Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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 Feb 19 at 3:26
add comment

4 Answers 4

up vote 16 down vote accepted

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

share|improve this answer
1  
Could you please provide a citation for this being NPC? –  Austin Buchanan Feb 11 at 19:07
8  
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 Feb 11 at 23:07
    
Very nice @Bangye ! –  R B Feb 12 at 22:39
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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