<p>Deciding the existence of 3-cycle cover is <a href="http://wwwhome.math.utwente.nl/~mantheyb/conferences/APPROX2002_BlaeserManthey_3CycleCovers.pdf">$NP$-complete</a> on directed graphs while it is polynomial time solvable on undirected graphs by a reduction to perfect matching.</p>

CC BY-SA 3.0
2014-02-11T21:49:50.620Z
2014-02-11T21:49:50.620Z
Mohammad Al-Turkistany
<p>In the Path Coloring problem we are given a tree T and a collection of paths on that tree (the idea is that T is a communication network and the paths are communication requests). We want to color the paths with a minimum number of colors so that two paths that share an edge take distinct colors.</p>

<p>This problem is known to be polynomial-time solvable if T is a bounded-degree undirected tree. It is however NP-complete if T is a bi-directed binary tree. I believe both results are given in the paper below.</p>

<p>[1] T. Erlebach and K. Jansen. "The complexity of path coloring and call
scheduling". Theoretical Computer Science, 255(1-2):33–50, 2001.</p>

CC BY-SA 3.0
2014-02-11T16:40:58.740Z
2014-02-11T16:40:58.740Z
Michael Lampis
<p>If I'm not mistaken, obtaining a constant factor approximation for the Steiner tree is NP-hard on directed graphs but is P-time on undirected graphs.</p>

CC BY-SA 3.0
2014-02-12T00:38:22.880Z
2014-02-12T00:38:22.880Z
Suresh Venkat
<p>The first problem comes to my mind is the 2-path problem (or more generally k-path problem). Given $(s_1,t_1)$ and $(s_2,t_2)$, find two disjoint paths from $s_1$ to $t_1$ and $s_2$ to $t_2$, respectively. The problem is NPC for directed graphs but polynomial-time solvable for undirected graphs (although not trivial).</p>

CC BY-SA 3.0
2014-02-12T22:39:40.077Z
Very nice @Bangye !
R B
CC BY-SA 3.0
2014-02-11T19:07:53.710Z
Could you please provide a citation for this being NPC?
Austin Buchanan
CC BY-SA 3.0
2014-02-11T23:07:16.173Z
See [ND40] "Disjoint Connecting Paths" in Garey and Johnson. But the status in the Comments is out of date. NPC for any fixed $k\geq 2$ can be found in: 
S. Fortune, J.E. Hopcroft, J. Wyllie, The directed subgraph homeomorphism problem, Theoret. Comput. Sci. 10 (1980) 111–121.
The complexity status of the undirected version has also been updated several times. It was shown that for any fixed $k$ the undirected version is polynomial. N. Robertson, P.D. Seymour, Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B 63 (1) (1995) 65–110.
Bangye
CC BY-SA 3.0
2014-02-11T16:34:17.480Z
2014-02-11T16:34:17.480Z
Bangye
<p>I'm looking for problems which are known to be NPC for directed graphs but has a polynomial algorithm for undirected graphs.</p>

<p>I've seen the question regarding the other way around here <a href="https://cstheory.stackexchange.com/questions/9257/directed-problems-that-are-easier-than-their-undirected-variant">“Directed” problems that are easier than their “undirected” variant</a>, but I'm looking for for hardness on the directed side.</p>

<p>For example, <a href="http://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK4/NODE182.HTM" rel="nofollow noreferrer">Feedback edge set</a> is known to be NPC on directed but polynomial time solvable on undirected graphs.</p>

<p>Which other <strong>natural</strong> problems have the same property?</p>

CC BY-SA 3.0
2014-02-19T03:26:07.507Z
st-connectivity is an interesting example for analogous lower-level classes - L for the undirected case versus NL-complete for the directed case.
Huck Bennett
<cc.complexity-theory><ds.algorithms><graph-theory><graph-algorithms><np-hardness>
Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs
R B
# Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs

(Asked by: username_0 on 2014-02-11)

I'm looking for problems which are known to be NPC for directed graphs but has a polynomial algorithm for undirected graphs.

I've seen the question regarding the other way around here [“Directed” problems that are easier than their “undirected” variant](https://cstheory.stackexchange.com/questions/9257/directed-problems-that-are-easier-than-their-undirected-variant), but I'm looking for for hardness on the directed side.

For example, [Feedback edge set](http://www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK4/NODE182.HTM) is known to be NPC on directed but polynomial time solvable on undirected graphs.

Which other **natural** problems have the same property?

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, graph-algorithms, np-hardness
> **Comments:**
> **username_1**: st-connectivity is an interesting example for analogous lower-level classes - L for the undirected case versus NL-complete for the directed case.  

---

## 4 answers

### Answer by username_5 on 2014-02-11. Score: 20 | Accepted answer

The first problem comes to my mind is the 2-path problem (or more generally k-path problem). Given $(s\_1,t\_1)$ and $(s\_2,t\_2)$, find two disjoint paths from $s\_1$ to $t\_1$ and $s\_2$ to $t\_2$, respectively. The problem is NPC for directed graphs but polynomial-time solvable for undirected graphs (although not trivial).

> **Comments:**
> **username_6**: Could you please provide a citation for this being NPC?  
> **username_5**: See [ND40] "Disjoint Connecting Paths" in Garey and Johnson. But the status in the Comments is out of date. NPC for any fixed $k\geq 2$ can be found in:  S. Fortune, J.E. Hopcroft, J. Wyllie, The directed subgraph homeomorphism problem, Theoret. Comput. Sci. 10 (1980) 111–121. The complexity status of the undirected version has also been updated several times. It was shown that for any fixed $k$ the undirected version is polynomial. N. Robertson, P.D. Seymour, Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B 63 (1) (1995) 65–110.  
> **username_0**: Very nice @Bangye !  

---

### Answer by username_2 on 2014-02-11. Score: 10

Deciding the existence of 3-cycle cover is [$NP$-complete](http://wwwhome.math.utwente.nl/~mantheyb/conferences/APPROX2002_BlaeserManthey_3CycleCovers.pdf) on directed graphs while it is polynomial time solvable on undirected graphs by a reduction to perfect matching.


---

### Answer by username_3 on 2014-02-11. Score: 3

In the Path Coloring problem we are given a tree T and a collection of paths on that tree (the idea is that T is a communication network and the paths are communication requests). We want to color the paths with a minimum number of colors so that two paths that share an edge take distinct colors.

This problem is known to be polynomial-time solvable if T is a bounded-degree undirected tree. It is however NP-complete if T is a bi-directed binary tree. I believe both results are given in the paper below.

[1] T. Erlebach and K. Jansen. "The complexity of path coloring and call
scheduling". Theoretical Computer Science, 255(1-2):33–50, 2001.


---

### Answer by username_4 on 2014-02-12. Score: 1

If I'm not mistaken, obtaining a constant factor approximation for the Steiner tree is NP-hard on directed graphs but is P-time on undirected graphs.


---

