Hamiltonian circuits in chordal bipartite graphs

AbstractThe main result of this paper is the NP-completeness of the HAMILTONIAN CIRCUIT problem for chordal bipartite graphs. This is proved by a sophisticated reduction from SATISFIABILITY. As a corollary, HAMILTONIAN CIRCUIT is NP-complete for strongly chordal split graphs. On both classes the complexity of the HAMILTONIAN PATH problem coincides with the complexity of HAMILTONIAN CIRCUIT. Further, we show that HAMILTONIAN CIRCUIT is linear-time solvable for convex bipartite graphs