3
$\begingroup$

The Hamiltonian cycle problem asks if a given graph contains a Hamiltonian cycle. The Hamiltonian cycle problem belongs to the class of NP-complete problems. However, for some special classes of graphs, the problem can be solved in polynomial time, for example, 4-connected planar graphs.

A graph is chordal if every cycle of length at least 4 has a chord. I would like to ask if the Hamiltonian cycle problem is still NP-hard for chordal graphs.

$\endgroup$

1 Answer 1

7
$\begingroup$

It's NP-complete even on split graphs.

For questions like this, always refer to the graph classes website. Chordal graphs at graph classes.org.

$\endgroup$

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.