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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – Gamow
    Apr 20, 2018 at 12:55
  • $\begingroup$ 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? $\endgroup$
    – rnbguy
    Apr 20, 2018 at 13:01
  • $\begingroup$ For K=1 your problem should be polynomially solvable. $\endgroup$
    – Gamow
    Apr 20, 2018 at 14:24
  • $\begingroup$ Of course! K=1 means, we already have a total order. But what about higher numbers? $\endgroup$
    – rnbguy
    Apr 20, 2018 at 14:30
  • 2
    $\begingroup$ @Annan: I have posted an answer instead of Ranadeep (I'm the paper author in question). $\endgroup$
    – a3nm
    May 11, 2018 at 12:43

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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