Heath, Lenwood S.Nema, Ajit Kumar2013-06-192013-06-192012http://hdl.handle.net/10919/19491A 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.ext/plainenIn CopyrightAlgorithmsData structuresTechnical reportTR-12-17http://eprints.cs.vt.edu/archive/00001204/01/TR-12-17.txt