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?
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).
External links referenced by this document:
Local articles referenced by this article: