17
$\begingroup$

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, but I'm looking for for hardness on the directed side.

For example, Feedback edge set is known to be NPC on directed but polynomial time solvable on undirected graphs.

Which other natural problems have the same property?

$\endgroup$
1
  • 2
    $\begingroup$ st-connectivity is an interesting example for analogous lower-level classes - L for the undirected case versus NL-complete for the directed case. $\endgroup$ Feb 19, 2014 at 3:26

4 Answers 4

20
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Could you please provide a citation for this being NPC? $\endgroup$ Feb 11, 2014 at 19:07
  • 8
    $\begingroup$ 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. $\endgroup$
    – Bangye
    Feb 11, 2014 at 23:07
  • $\begingroup$ Very nice @Bangye ! $\endgroup$
    – R B
    Feb 12, 2014 at 22:39
10
$\begingroup$

Deciding the existence of 3-cycle cover is $NP$-complete on directed graphs while it is polynomial time solvable on undirected graphs by a reduction to perfect matching.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.