Theoretical Computer Science
cc.complexity-theory ds.algorithms graph-theory graph-algorithms np-hardness
Updated Thu, 23 Jun 2022 08:13:23 GMT

Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs


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?

Solution

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 (3)

  • +1 – Could you please provide a citation for this being NPC? — Feb 11, 2014 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) 111121. 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) 65110. — Feb 11, 2014 at 23:07  
  • +0 – Very nice @Bangye ! — Feb 12, 2014 at 22:39  

External Links

External links referenced by this document:

Linked Articles

Local articles referenced by this article:

References