## Exact algorithms for finding longest cycles in claw-free graphs

*Hajo Broersma, Fedor V. Fomin, Pim van 't Hof and Daniël Paulusma*

*Algorithmica*, vol. 65, no. 1, pp. 129-145, 2013.

[__DOI__][__Preprint__]

A preliminary version of this paper, entitled "Fast exact algorithms for hamiltonicity in claw-free graphs", appeared in the proceedings of
WG 2009, the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (held on 24-26 June, 2009 in Montpellier, France), *Lecture Notes in Computer Science*, vol. 5911, pp. 44-53, 2009.

[__DOI__]
[__Photos__]
[David Eppstein mentions my talk about another paper in his __blog__]

### Abstract:

The Hamiltonian Cycle problem is the problem of deciding whether an *n*-vertex graph *G* has a cycle passing through all vertices of *G*. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in *O*^{*}(α* ^{n}*) time for some constant α<2
was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses

*O*

^{*}(1.657

*) time and polynomial space. The Longest Cycle problem, in which the task is to find a cycle of maximum length, is a natural generalization of the Hamiltonian Cycle problem. For a claw-free graph*

^{n}*G*, finding a longest cycle is equivalent to finding a closed trail (i.e., a connected even subgraph, possibly consisting of a single vertex) that dominates the largest number of edges of some associated graph

*H*. Using this translation we obtain two exact algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses

*O*

^{*}(1.6818

*) time and exponential space, and one algorithm that uses*

^{n}*O*

^{*}(1.8878

*) time and polynomial space.*

^{n}