<p>You may find the following recent reference useful:</p>
<p>M. Caceres, M. Cairo, B. Mumey, R.  Rizzi, and A. Tomescu. On the parameterized complexity of the Minimum Path Cover problem in DAGs.</p>
<p>arXiv preprint arXiv:2007.07575</p>

CC BY-SA 4.0
2020-10-17T00:59:32.877Z
Thank you very much! This paper is exactly what I'm looking for.
shgr1092
CC BY-SA 4.0
2020-10-16T18:56:51.040Z
2020-10-16T18:56:51.040Z
Gabriel Istrate
<p>Given a partially ordered set <span class="math-container">$P$</span> with <span class="math-container">$n=|P|$</span> and width <span class="math-container">$w$</span>:</p>
<p>-What is the best known complexity (in expectation) for finding a chain decomposition of <span class="math-container">$w$</span> chains?</p>
<p>-What is the best known complexity (in expectation) for finding a chain decomposition of <span class="math-container">$O(w)$</span> chains?</p>
<p>The paper &quot;On the Decomposition of Posets&quot; (2012) seems to provide an algorithm in worst-case <span class="math-container">$O(wn^2)$</span> time for the first question but is there better for either?</p>
<p>Another question, possibly naive: does the chain decomposition produced by topological sort have any guarantees on the number of chains it consists of?</p>

CC BY-SA 4.0
2020-10-14T20:27:39.043Z
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
CC BY-SA 4.0
2020-10-15T07:08:21.910Z
@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
<partial-order>
Time complexity of finding chain decomposition of partially ordered set
shgr1092
# Time complexity of finding chain decomposition of partially ordered set

(Asked by: username_0 on 2020-10-14)

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?

**Tags:** partial-order

> **Comments:**
> **username_1**: 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  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2020-10-16. Score: 1 | Accepted answer

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

> **Comments:**
> **username_0**: Thank you very much! This paper is exactly what I'm looking for.  

---

