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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.