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 languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009. Revised Papers
EditorsChristophe Paul, Michel Habib
Place of PublicationBerlin
PublisherSpringer
Pages44-53
Number of pages10
ISBN (Electronic)978-3-642-11409-0
ISBN (Print)978-3-642-11408-3
DOIs
Publication statusPublished - Feb 2010
Event35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009 - Montpellier, France
Duration: 24 Jun 200926 Jun 2009
Conference number: 35

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume5911
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference35th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2009
Abbreviated titleWG
CountryFrance
CityMontpellier
Period24/06/0926/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

Keywords

  • 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