Efficient Hamiltonian cycle algorithms for graph classes

Generally speaking, finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $H$, then we can reduce the problem of finding a Hamiltonian cycle in $G$ to finding an Euler tour of $H$, which is easy.

Question is: are there similar shortcuts known for other graph classes?

6 Answers

The graph classes webpage has a page with a list of some graph classes for which the complexity of Hamiltonian Cycle is known. It currently lists some 400+ graph classes for which the problem is known to be polynomial time solvable.

Edit: I misread your question as whether there are other graph classes for which Hamiltonian Cycle is polytime solvable, but realized now that that was maybe not what you ment. I will leave this answer nevertheless as it might be of interest. Perhaps more related to your question is that maximum independent set (NP-hard on general graphs) in a line graph corresponds to a maximum matching in its host graph. Hence, independent set is also solvable in polytime on line graphs.

One class of graphs for which many NP-hard problems (including finding a Hamiltonian cycle) are easy (linear-time) are graphs of bounded tree-width. Indeed, by Courcelle's theorem any problem which can be expressed in a certain logic called monadic second-order logic ($MSO_2$) can be solved in linear-time on the class of graphs of tree-width at most $k$ (for any fixed $k$).

For your specific question, for a subset $F$ of edges of a graph $G$, it is fairly straightforward to encode in $MSO_2$ the property that $F$ is connected and it is also easy to express the property that every vertex of $G$ is incident to exactly two edges in $F$. Taking the conjunction of these properties gives the property that $F$ is a Hamiltonian cycle.

I am not sure your reduction to Euler cycle is complete.

According to Wikipedia

If a graph G has an Euler cycle, that is, if G is connected and has an even number of edges at each vertex, then the line graph of G is Hamiltonian. (However, not all Hamiltonian cycles in line graphs come from Euler cycles in this way.)

This does appear iff to me and $G$ can be non-eulerian, while $L(G)$ might have Hamiltonian cycles for different reasons.

Added

A paper claims:

It is shown that the existence of a Hamilton cycle in the line graph of a graph G can be ensured by imposing certain restrictions on certain induced subgraphs of G.

• Thanks for pointing this out! I was indeed going a bit too quickly; I had in mind the proof of Petersen's 2k-factor theorem which sets up just the correspondence I've envisaged in a special case. Generally speaking the theorem of Harary and Nash-Williams (quoted on p. 414 in the paper you linked to) describes the (more complex) correspondence. – Felix Goldberg Sep 30 '13 at 9:34

In fact, it can be proved that Hamiltonian Cycle remains $\mathsf{NP}$-hard even for a very restricted subclass of line graphs: line graphs of $1$-subdivisions of planar cubic bipartite graphs. These graphs are cubic. Not surprisingly the same holds if we pass to $4$-regular line graphs: Hamiltonian Cycle remains $\mathsf{NP}$-hard for line graphs of planar cubic bipartite graphs.

Both results can be obtained by reductions from Hamiltonian Cycle restricted to planar cubic bipartite graphs:

T. Akiyama, T. Nishizeki, N. Saito, NP-Completeness of the Hamiltonian Cycle Problem for Bipartite Graphs, Journal of Information Processing 3 (1980) 73-76.

There are linear-time algorithms based on Whitney's and Tutte's theorems on 4-connected planar graphs:

Asano, Takao, Shunji Kikuchi, and Nobuji Saito. "A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs." Discrete Applied Mathematics 7.1 (1984): 1-15. (Elsevier link)

Chiba, Norishige, and Takao Nishizeki. "The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs." Journal of Algorithms 10.2 (1989): 187-211. (Elsevier link)

There’s a polynomial time algorithm for finding a Hamiltonian cycle in solid grid graphs (grid graphs without holes):

Umans, Christopher, and William Lenhart. "Hamiltonian cycles in solid grid graphs." Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on. IEEE, 1997.