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 &quot;On the Decomposition of Posets&quot; (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?
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