# Constrained Topological Sorting with bounded number of chains

In general, constrained topological sorting is NP-hard.

Now we add another constraint to it, such that take any k+1 nodes and there will be at least one pair (u, v)such that there is a path from u to v -- that is, there can be maximum k number of chains.

I want to know, is it still NP Hard?

Edit: I have my answer. Decision version of this question is in NL which implies it is in PTIME.

• Of course it is still NP-hard. Even the special case where k equals the square of the total number of nodes is NP-hard. – Gamow Apr 20 '18 at 12:55
• I see. Do you have any (short/intuitive) proof? Also, do you think there is any bound K such that, if k < K, the problem is P? Like can we say anything when k = 2 or 3? – rnbguy Apr 20 '18 at 13:01
• For K=1 your problem should be polynomially solvable. – Gamow Apr 20 '18 at 14:24
• Of course! K=1 means, we already have a total order. But what about higher numbers? – rnbguy Apr 20 '18 at 14:30
• @Annan: I have posted an answer instead of Ranadeep (I'm the paper author in question). – a3nm May 11 '18 at 12:43

The additional constraint amounts to saying that the input DAG has width $\leq k$, i.e., there is no antichain of size $k+1$. In this case, if $k$ is a constant, the decision version of the constrained topological sorting problem is in NL by Prop C.2 of https://arxiv.org/abs/1707.04310, which amounts to a PTIME dynamic programming algorithm. Reconstructing a matching topological sort as part of the dynamic programming algorithm will also be in PTIME