0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – David Eppstein Oct 14 at 20:27
  • $\begingroup$ @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. $\endgroup$ – shgr1092 Oct 15 at 7:08
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much! This paper is exactly what I'm looking for. $\endgroup$ – shgr1092 Oct 17 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.