# Problems with different complexities on directed and mixed graphs

Some computational problems have different complexity on different graph classes. For instance, 3-edge coloring is NP-complete on cubic graphs but polynomial on cubic bipartite graphs.

What are the graph problems that have different complexities on directed and mixed graphs.

A mixed graph can have both directed and undirected edges. A perfect answer would be a survey paper of such problems.

• Shortest path, under the assumption that $\mathsf{L\neq NL}$. – Ariel Dec 28 '17 at 8:30
• @Ariel I am interested in P, NPI, and NP-complete problems. – Mohammad Al-Turkistany Dec 28 '17 at 8:34