3
$\begingroup$

Three problems --- Graph coloring, Stable set, and Clique --- are known NP-hard problems (on general graphs) that can be solved in polynomial time, when we know that the given graph is a perfect graph.

Are there other NP-hard problems (on general graphs) which are either known to be poly-time solvable on perfect graphs or known to be NP-hard even when restricted to perfect graphs?

For example, is the problem of deciding the presence of a Hamiltonian cycle in a perfect graph poly-time solvable or is it NP-hard, when restricted to perfect graphs?

$\endgroup$

1 Answer 1

6
$\begingroup$

ISGCI is the go-to site for finding such results.

On the perfect graph page, you can find that the Hamiltonian cycle problem is NP-hard for perfect graphs, because the problem is already NP-hard for bipartite graphs and every bipartite graph is perfect.

$\endgroup$
1
  • $\begingroup$ ISGCI looks like a really amazing resource! Didn't know about that. Thanks! $\endgroup$
    – Lisa E.
    Commented Jun 6 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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