<p>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 <a href="https://arxiv.org/abs/1707.04310" rel="nofollow noreferrer">https://arxiv.org/abs/1707.04310</a>, 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</p>

CC BY-SA 4.0
2018-05-11T12:42:45.643Z
2018-05-11T12:42:45.643Z
Antoine Amarilli 'a3nm'
<p>In general, constrained topological sorting is <a href="https://arxiv.org/abs/1707.04310" rel="nofollow noreferrer">NP-hard</a>.</p>

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

<p>I want to know, is it still NP Hard?</p>

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

CC BY-SA 3.0
2018-04-20T12:55:53.803Z
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
CC BY-SA 3.0
2018-04-20T13:01:13.873Z
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
CC BY-SA 3.0
2018-04-20T14:24:02.000Z
For K=1 your problem should be polynomially solvable.
Gamow
CC BY-SA 3.0
2018-04-20T14:30:21.833Z
Of course! K=1 means, we already have a total order. But what about higher numbers?
rnbguy
CC BY-SA 4.0
2018-05-03T13:41:07.157Z
@Gamow I asked the paper author in an another post. The paper already describes the decision version of my question. It is PTIME. I can see generating a constrained topological sort will be in PTIME too.
rnbguy
CC BY-SA 4.0
2018-05-08T17:52:21.890Z
If you have an answer please post your answer in detail and then accept it. This will be useful for future readers and mark clearly in the search that the question has been answered.
AnnanFay
CC BY-SA 4.0
2018-05-11T12:43:51.977Z
@Annan: I have posted an answer instead of Ranadeep (I'm the paper author in question).
Antoine Amarilli 'a3nm'
<np-hardness><complexity-classes><topological-graph-theory><topological-sorting>
Constrained Topological Sorting with bounded number of chains
rnbguy
# Constrained Topological Sorting with bounded number of chains

(Asked by: username_0 on 2018-04-20)

In general, constrained topological sorting is [NP-hard](https://arxiv.org/abs/1707.04310).

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.

**Tags:** np-hardness, complexity-classes, topological-graph-theory, topological-sorting

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: For K=1 your problem should be polynomially solvable.  
> **username_0**: Of course! K=1 means, we already have a total order. But what about higher numbers?  
> **username_0**: @username_1 I asked the paper author in an another post. The paper already describes the decision version of my question. It is PTIME. I can see generating a constrained topological sort will be in PTIME too.  
> **username_2**: If you have an answer please post your answer in detail and then accept it. This will be useful for future readers and mark clearly in the search that the question has been answered.  
> **username_3**: @Annan: I have posted an answer instead of Ranadeep (I'm the paper author in question).  

---

## 1 answers

### Answer by username_3 on 2018-05-11. Score: 3 | Accepted answer

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


---

