7
$\begingroup$

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?

$\endgroup$

7 Answers 7

4
$\begingroup$

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 meant. 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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Sep 30, 2013 at 9:34
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Even though the Hamilton path problem is NP-hard, in practice it is usually easy. An efficient algorithm has been known for 50 years. It is "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21 (Oct. 1974), pp 576-580; DOI: 10.1145/321850.321854. It works for both directed and undirected graphs.

$\endgroup$
1
  • 6
    $\begingroup$ Let me disclose that you are the author of the article that you are citing. $\endgroup$
    – Alex M.
    Commented Mar 28 at 9:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .