ON COMPLEXITY OF SOME CHAIN AND ANTICHAIN PARTITION PROBLEMS

In the paper we deal with computational complexity of a problem C(k) (respectively A(k)) of a partition of an ordered set into minimum number of at most k-element chains (resp. antichains). We show that C(k), k greater-than-or-equal-to 3, is NP-complete even for N-free ordered sets of length at most k, C(k) and A(k) are polynomial for series-paralel orders and A(k) is polynomial for interval orders. We also consider related problems for graphs.