# Time complexity of finding chain decomposition of partially ordered set

Given a partially ordered set $$P$$ with $$n=|P|$$ and width $$w$$:

-What is the best known complexity (in expectation) for finding a chain decomposition of $$w$$ chains?

-What is the best known complexity (in expectation) for finding a chain decomposition of $$O(w)$$ chains?

The paper "On the Decomposition of Posets" (2012) seems to provide an algorithm in worst-case $$O(wn^2)$$ time for the first question but is there better for either?

Another question, possibly naive: does the chain decomposition produced by topological sort have any guarantees on the number of chains it consists of?

• The best time bound I know is the one you state, O(wn^2), but with an earlier reference: Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003), "Recognition algorithms for orders of small width and graphs of small Dilworth number", Order, 20 (4): 351–364 (2004), doi:10.1023/B:ORDE.0000034609.99940.fb – David Eppstein Oct 14 at 20:27
• @DavidEppstein I see that that is an older reference, thanks! I guess the fastest known algorithms are O(n^5/2) and O(wn^2) then? I'm wondering if any loosening of conditions would help? For example, if there are randomised algorithms that work well in expectation. Or, in particular, I need a partitioning into O(k) chains in O(kn) expected time where k<=O(w*log^zn) where z is constant, or similar. – shgr1092 Oct 15 at 7:08

You may find the following recent reference useful:

M. Caceres, M. Cairo, B. Mumey, R. Rizzi, and A. Tomescu. On the parameterized complexity of the Minimum Path Cover problem in DAGs.

arXiv preprint arXiv:2007.07575

• Thank you very much! This paper is exactly what I'm looking for. – shgr1092 Oct 17 at 0:59