# 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 Oct 14 '20 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. Oct 15 '20 at 7:08