Fast exact algorithms for hamiltonicity in claw-free graphs

Haitze J. Broersma, Fedor V. Fomin, Pim van 't Hof, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

Abstract

The Hamiltonian Cycle problem asks if an $n$-vertex graph $G$ has a cycle passing through all vertices of $G$. This problem is a classic $NP$-complete problem. So far, finding an exact algorithm that solves it in $O^*(\aplha^n)$ time for some constant $\alpha < 2$ is a notorious open problem. For a claw-free graph $G$, finding a hamiltonian cycle is equivalent to finding a closed trail (eulerian subgraph) that dominates the edges of some associated graph $H$. Using this translation we obtain two exact algorithms that solve the Hamiltonian Cycle problem for the class of claw-free graphs: one algorithm that uses $O^*(1.6818^n)$ time and exponential space, and one algorithm that uses $O^*(1.8878^n)$ time and polynomial space.
Original language English Graph-Theoretic Concepts in Computer Science 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers Christophe Paul, Michel Habib Berlin Springer 44-53 10 978-3-642-11409-0 978-3-642-11408-3 https://doi.org/10.1007/978-3-642-11409-0_4 Published - Feb 2010 35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009 - Montpellier, FranceDuration: 24 Jun 2009 → 26 Jun 2009Conference number: 35

Publication series

Name Lecture Notes in Computer Science Springer Verlag 5911 0302-9743 1611-3349

Conference

Conference 35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009 WG France Montpellier 24/06/09 → 26/06/09

Fingerprint

Hamiltonicity
Claw-free Graphs
Hamiltonian circuit
Exact Algorithms
Fast Algorithm
Graph in graph theory
Subgraph
Open Problems
NP-complete problem
Cycle
Closed
Polynomial
Vertex of a graph

• IR-71167
• EWI-17828
• METIS-270799

Cite this

Broersma, H. J., Fomin, F. V., van 't Hof, P., & Paulusma, D. (2010). Fast exact algorithms for hamiltonicity in claw-free graphs. In C. Paul, & M. Habib (Eds.), Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers (pp. 44-53). (Lecture Notes in Computer Science; Vol. 5911). Berlin: Springer. https://doi.org/10.1007/978-3-642-11409-0_4
Broersma, Haitze J. ; Fomin, Fedor V. ; van 't Hof, Pim ; Paulusma, Daniël. / Fast exact algorithms for hamiltonicity in claw-free graphs. Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers. editor / Christophe Paul ; Michel Habib. Berlin : Springer, 2010. pp. 44-53 (Lecture Notes in Computer Science).
@inproceedings{4939c61c45c04cb0a79922fc768c0888,
title = "Fast exact algorithms for hamiltonicity in claw-free graphs",
abstract = "The Hamiltonian Cycle problem asks if an $n$-vertex graph $G$ has a cycle passing through all vertices of $G$. This problem is a classic $NP$-complete problem. So far, finding an exact algorithm that solves it in $O^*(\aplha^n)$ time for some constant $\alpha < 2$ is a notorious open problem. For a claw-free graph $G$, finding a hamiltonian cycle is equivalent to finding a closed trail (eulerian subgraph) that dominates the edges of some associated graph $H$. Using this translation we obtain two exact algorithms that solve the Hamiltonian Cycle problem for the class of claw-free graphs: one algorithm that uses $O^*(1.6818^n)$ time and exponential space, and one algorithm that uses $O^*(1.8878^n)$ time and polynomial space.",
keywords = "IR-71167, EWI-17828, METIS-270799",
author = "Broersma, {Haitze J.} and Fomin, {Fedor V.} and {van 't Hof}, Pim and Dani{\"e}l Paulusma",
note = "10.1007/978-3-642-11409-0_4",
year = "2010",
month = "2",
doi = "10.1007/978-3-642-11409-0_4",
language = "English",
isbn = "978-3-642-11408-3",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "44--53",
editor = "Christophe Paul and Michel Habib",
booktitle = "Graph-Theoretic Concepts in Computer Science",

}

Broersma, HJ, Fomin, FV, van 't Hof, P & Paulusma, D 2010, Fast exact algorithms for hamiltonicity in claw-free graphs. in C Paul & M Habib (eds), Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers. Lecture Notes in Computer Science, vol. 5911, Springer, Berlin, pp. 44-53, 35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009, Montpellier, France, 24/06/09. https://doi.org/10.1007/978-3-642-11409-0_4

Fast exact algorithms for hamiltonicity in claw-free graphs. / Broersma, Haitze J.; Fomin, Fedor V.; van 't Hof, Pim; Paulusma, Daniël.

Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers. ed. / Christophe Paul; Michel Habib. Berlin : Springer, 2010. p. 44-53 (Lecture Notes in Computer Science; Vol. 5911).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Fast exact algorithms for hamiltonicity in claw-free graphs

AU - Broersma, Haitze J.

AU - Fomin, Fedor V.

AU - van 't Hof, Pim

AU - Paulusma, Daniël

N1 - 10.1007/978-3-642-11409-0_4

PY - 2010/2

Y1 - 2010/2

N2 - The Hamiltonian Cycle problem asks if an $n$-vertex graph $G$ has a cycle passing through all vertices of $G$. This problem is a classic $NP$-complete problem. So far, finding an exact algorithm that solves it in $O^*(\aplha^n)$ time for some constant $\alpha < 2$ is a notorious open problem. For a claw-free graph $G$, finding a hamiltonian cycle is equivalent to finding a closed trail (eulerian subgraph) that dominates the edges of some associated graph $H$. Using this translation we obtain two exact algorithms that solve the Hamiltonian Cycle problem for the class of claw-free graphs: one algorithm that uses $O^*(1.6818^n)$ time and exponential space, and one algorithm that uses $O^*(1.8878^n)$ time and polynomial space.

AB - The Hamiltonian Cycle problem asks if an $n$-vertex graph $G$ has a cycle passing through all vertices of $G$. This problem is a classic $NP$-complete problem. So far, finding an exact algorithm that solves it in $O^*(\aplha^n)$ time for some constant $\alpha < 2$ is a notorious open problem. For a claw-free graph $G$, finding a hamiltonian cycle is equivalent to finding a closed trail (eulerian subgraph) that dominates the edges of some associated graph $H$. Using this translation we obtain two exact algorithms that solve the Hamiltonian Cycle problem for the class of claw-free graphs: one algorithm that uses $O^*(1.6818^n)$ time and exponential space, and one algorithm that uses $O^*(1.8878^n)$ time and polynomial space.

KW - IR-71167

KW - EWI-17828

KW - METIS-270799

U2 - 10.1007/978-3-642-11409-0_4

DO - 10.1007/978-3-642-11409-0_4

M3 - Conference contribution

SN - 978-3-642-11408-3

T3 - Lecture Notes in Computer Science

SP - 44

EP - 53

BT - Graph-Theoretic Concepts in Computer Science

A2 - Paul, Christophe

A2 - Habib, Michel

PB - Springer

CY - Berlin

ER -

Broersma HJ, Fomin FV, van 't Hof P, Paulusma D. Fast exact algorithms for hamiltonicity in claw-free graphs. In Paul C, Habib M, editors, Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers. Berlin: Springer. 2010. p. 44-53. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-11409-0_4