A partial order or poset P=(X, on a (finite) base set X?determines the set L(P)?of linear extensions of P. The problem of computing, for a poset P, the cardinality of L(P)?is #P-complete. A set {P1,P2,...,Pk}?of poset...A partial order or poset P=(X, on a (finite) base set X?determines the set L(P)?of linear extensions of P. The problem of computing, for a poset P, the cardinality of L(P)?is #P-complete. A set {P1,P2,...,Pk}?of posets on X?covers the set of linear orders that is the union of the L(Pi). Given linear orders L1,L2,...,Lm on X, the Poset Cover problem is to determine the smallest number of posets that cover {L1,L2,...,Lm}. Here, we show that the decision version of this problem is NP-complete. On the positive side, we explore the use of cover relations for finding posets that cover a set of linear orders and present a polynomial-time algorithm to find a partial poset cover.展开更多
文摘A partial order or poset P=(X, on a (finite) base set X?determines the set L(P)?of linear extensions of P. The problem of computing, for a poset P, the cardinality of L(P)?is #P-complete. A set {P1,P2,...,Pk}?of posets on X?covers the set of linear orders that is the union of the L(Pi). Given linear orders L1,L2,...,Lm on X, the Poset Cover problem is to determine the smallest number of posets that cover {L1,L2,...,Lm}. Here, we show that the decision version of this problem is NP-complete. On the positive side, we explore the use of cover relations for finding posets that cover a set of linear orders and present a polynomial-time algorithm to find a partial poset cover.
