Cardinality-restricted chains and antichains in partially ordered sets

AbstractFor a given poset and positive integer κ, four problems are considered. Covering: Determine a minimum cardinality cover of the poset elements by chains (antichains), each of length (width) at most κ. Optimization: Given also weights on the poset elements, find a chain (antichain) of maximum total weight among those of length (width) at most κ. It is shown that the chain covering problem is NP-complete, while chain optimization is polynomial-time solvable. Several classes of facets are derived for the polytope generated by incidence vectors of antichains of width at most κ. Certain of these facets are then used to develop a polyhedral combinatorial algorithm for the antichain optimization problem. Computational results are given for the algorithm on randomly generated posets with up to 1005 elements and 4 ⩽ κ ⩽ 30