The Poset Cover Problem

Abstract

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.