TITLE:
The Poset Cover Problem
AUTHORS:
Lenwood S. Heath, Ajit Kumar Nema
KEYWORDS:
Linear Orders; Partial Orders; NP-Completeness; Algorithms
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.3 No.3,
July
2,
2013
ABSTRACT:
A partial order or poset P=(X, on a (finite) base set Xdetermines 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 Xcovers 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.