<p>This only aims at partially answering the first question of the post:</p>

<blockquote>
  <p>What are some directed problems that remain NP-hard on DAGs ?</p>
</blockquote>

<p>In [1], a few natural problems on directed graphs are given that remain NP-hard on DAGs. The motivation of the paper is to find a "good" treewidth-like measure for digraphs. They argue that the drawback of many measures for digraphs is that they are constant for DAGs, but many directed counterparts of natural problems remain NP-hard on DAGs. For more on this topic, see also [2] and the references of these papers.</p>

<p>[1] Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith: On Digraph Width Measures in Parameterized Algorithmics. IWPEC 2009:185-197. <a href="http://www.fi.muni.cz/~hlineny/Research/papers/kenny-full.pdf" rel="nofollow">Full version</a></p>

<p>[2] Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar: Are there any good digraph width measures?. IPEC 2010, to appear. <a href="http://arxiv.org/abs/1004.1485" rel="nofollow">arXiv</a></p>

CC BY-SA 3.0
2010-10-05T10:13:14.293Z
2016-08-11T14:42:28.007Z
2016-08-11T14:42:28.007Z
Serge Gaspers
<p>Several routing problems are known to be NP-hard and even hard to approximate to polynomial factors in DAGs. These include problems such as maximum edge-disjoint paths and congestion-minimization. See the papers by Andrews, Chuzhoy, Khanna, Zhang and others for more pointers.</p>

CC BY-SA 3.0
2011-08-04T18:13:29.840Z
2011-08-04T18:13:29.840Z
Chandra Chekuri
<p>The famous OPEN[8] problem from list of Garey and Johnson is beyond P, but open to be proved to be NP-C.
That problem is on DAG. Each round you can delete at most three vertices which do not have incoming edge. Decide whether all the vertices of the DAG could be deleted in K rounds?
OPEN from 1970s.</p>

CC BY-SA 3.0
2011-08-04T15:07:32.993Z
2011-08-04T15:07:32.993Z
Peng Zhang
<p>From the logic point of view, evaluate a MSO formula is NP-hard on DAGs.
For example, $\varphi:=\exists C_1 C_2 C_3 [\forall x (C_1 x \lor C_2 x \lor C_3 x) \land \bigwedge_{i=1,2,3}\forall x,y(\neg C_i x \lor \neg C_i y\lor \neg E(x,y))]$ says graph G can be 3-colored. And for any undirected graph $G$, we can directed its edges to get a DAG $G'$,
and change all $E(x,y)$ in $\varphi$ to $E(x,y)\lor E(y,x)$. Now we have $G\models\varphi\iff G'\models\varphi'$.</p>

CC BY-SA 2.5
2010-10-05T07:53:20.020Z
It seems that this problem is not using the directions of the edges. I am looking for directed problems.
Shiva Kintali
CC BY-SA 2.5
2010-10-05T14:08:12.907Z
@Shiva: Why does this not meet your criteria for a directed problem?
András Salamon
CC BY-SA 2.5
2010-10-05T19:18:35.120Z
@András : Graph coloring cares about the presence of an edge (u,v). It does not matter if the edge is directed from u to v or from v to u. On the other hand, Hamiltonian Path uses the directions of the edges. It is possible to change the directions of some edges and convert an YES instance into a NO instance.
Shiva Kintali
CC BY-SA 2.5
2010-10-06T05:49:09.057Z
@Shiva: So you want a property that is expressed by a formula that isn't symmetric (invariant under permutation of variables)?
András Salamon
CC BY-SA 2.5
2010-10-06T07:33:55.133Z
@András : Exactly.
Shiva Kintali
CC BY-SA 2.5
2010-10-05T07:38:37.430Z
2010-10-05T07:38:37.430Z
Regularity
<p><a href="http://en.wikipedia.org/wiki/Tree_decomposition" rel="nofollow noreferrer">Tree width</a> measures how close a graph is to a tree. Several NP-hard problems are tractable on graphs with bounded tree width. If a problem remains NP-hard on trees then tree width cannot save us. This was the motivation behind one of my <a href="https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees">previous questions</a> asking for NP-hard problems on trees.</p>

<p>There are several directed versions of tree width measuring how close a directed graph is to a directed acyclic graph (DAG). What are some <em>directed</em> problems that remain NP-hard on DAGs ? A directed problem makes essential use of the directions of the edges. For example, hamiltonian path is a directed problem whereas vertex cover is not. One of the answers to my <a href="https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees">previous question</a> gave a general recipe for generating problems that are hard on trees. Is there such a recipe for DAGs ?</p>

<np-hardness><directed-acyclic-graph>
Directed NP-hard problems on DAGs
Shiva Kintali
# Directed NP-hard problems on DAGs

(Asked by: username_0 on 2010-10-05)

[Tree width](http://en.wikipedia.org/wiki/Tree_decomposition) measures how close a graph is to a tree. Several NP-hard problems are tractable on graphs with bounded tree width. If a problem remains NP-hard on trees then tree width cannot save us. This was the motivation behind one of my [previous questions](https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees) asking for NP-hard problems on trees.

There are several directed versions of tree width measuring how close a directed graph is to a directed acyclic graph (DAG). What are some *directed* problems that remain NP-hard on DAGs ? A directed problem makes essential use of the directions of the edges. For example, hamiltonian path is a directed problem whereas vertex cover is not. One of the answers to my [previous question](https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees) gave a general recipe for generating problems that are hard on trees. Is there such a recipe for DAGs ?

**Tags:** np-hardness, directed-acyclic-graph

---

## 4 answers

### Answer by username_1 on 2010-10-05. Score: 7 | Accepted answer

This only aims at partially answering the first question of the post:

> What are some directed problems that remain NP-hard on DAGs ?

In [1], a few natural problems on directed graphs are given that remain NP-hard on DAGs. The motivation of the paper is to find a "good" treewidth-like measure for digraphs. They argue that the drawback of many measures for digraphs is that they are constant for DAGs, but many directed counterparts of natural problems remain NP-hard on DAGs. For more on this topic, see also [2] and the references of these papers.

[1] Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith: On Digraph Width Measures in Parameterized Algorithmics. IWPEC 2009:185-197. [Full version](http://www.fi.muni.cz/~hlineny/Research/papers/kenny-full.pdf)

[2] Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar: Are there any good digraph width measures?. IPEC 2010, to appear. [arXiv](http://arxiv.org/abs/1004.1485)


---

### Answer by username_2 on 2011-08-04. Score: 6

Several routing problems are known to be NP-hard and even hard to approximate to polynomial factors in DAGs. These include problems such as maximum edge-disjoint paths and congestion-minimization. See the papers by Andrews, Chuzhoy, Khanna, Zhang and others for more pointers.


---

### Answer by username_3 on 2011-08-04. Score: 2

The famous OPEN[8] problem from list of Garey and Johnson is beyond P, but open to be proved to be NP-C.
That problem is on DAG. Each round you can delete at most three vertices which do not have incoming edge. Decide whether all the vertices of the DAG could be deleted in K rounds?
OPEN from 1970s.


---

### Answer by username_4 on 2010-10-05. Score: 1

From the logic point of view, evaluate a MSO formula is NP-hard on DAGs.
For example, $\varphi:=\exists C\_1 C\_2 C\_3 [\forall x (C\_1 x \lor C\_2 x \lor C\_3 x) \land \bigwedge\_{i=1,2,3}\forall x,y(\neg C\_i x \lor \neg C\_i y\lor \neg E(x,y))]$ says graph G can be 3-colored. And for any undirected graph $G$, we can directed its edges to get a DAG $G'$,
and change all $E(x,y)$ in $\varphi$ to $E(x,y)\lor E(y,x)$. Now we have $G\models\varphi\iff G'\models\varphi'$.

> **Comments:**
> **username_0**: It seems that this problem is not using the directions of the edges. I am looking for directed problems.  
> **username_5**: @Shiva: Why does this not meet your criteria for a directed problem?  
> **username_0**: @András : Graph coloring cares about the presence of an edge (u,v). It does not matter if the edge is directed from u to v or from v to u. On the other hand, Hamiltonian Path uses the directions of the edges. It is possible to change the directions of some edges and convert an YES instance into a NO instance.  
> **username_5**: @Shiva: So you want a property that is expressed by a formula that isn't symmetric (invariant under permutation of variables)?  
> **username_0**: @András : Exactly.  

---

