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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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

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