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 '18 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 '18 at 13:01
  • $\begingroup$ For K=1 your problem should be polynomially solvable. $\endgroup$ – Gamow Apr 20 '18 at 14:24
  • $\begingroup$ Of course! K=1 means, we already have a total order. But what about higher numbers? $\endgroup$ – rnbguy Apr 20 '18 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 '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


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.