The Poset Cover Problem

• 作者: Ajit Kumar Nema Lenwood S. Heath
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: LINEAR ORDERS PARTIAL ORDERS NP-COMPLETENESS ALGORITHMS
• 年，卷（期）: 2013,（3）
• 页码范围: 101-111
• 页数: 11页
• 分类号: O1

摘要

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.