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
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.