Exact algorithms for finding longest cycles in claw-free graphs

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

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

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 (n) time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses (1657n) 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 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 deterministic algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses (16818n) time and exponential space, and one algorithm that uses (18878n) time and polynomial space.
Original languageUndefined
Pages (from-to)129-145
Number of pages17
JournalAlgorithmica
Volume65
Issue number1
DOIs
Publication statusPublished - 2013

Keywords

  • EWI-21076
  • MSC-05C
  • (Hamilton) cycle
  • Exact algorithm
  • IR-86129
  • NP-complete
  • NP-hard
  • Hamiltonian graph
  • METIS-297586
  • Computational Complexity

Cite this

Broersma, Haitze J. ; Fomin, Fedor V. ; van 't Hof, Pim ; Paulusma, Daniël. / Exact algorithms for finding longest cycles in claw-free graphs. In: Algorithmica. 2013 ; Vol. 65, No. 1. pp. 129-145.
@article{5bd47842fc9744cfb7ed681ed3a55fd9,
title = "Exact algorithms for finding longest cycles in claw-free graphs",
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 (n) time for some constant α<2 was a notorious open problem until very recently, when Bj{\"o}rklund presented a randomized algorithm that uses (1657n) 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 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 deterministic algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses (16818n) time and exponential space, and one algorithm that uses (18878n) time and polynomial space.",
keywords = "EWI-21076, MSC-05C, (Hamilton) cycle, Exact algorithm, IR-86129, NP-complete, NP-hard, Hamiltonian graph, METIS-297586, Computational Complexity",
author = "Broersma, {Haitze J.} and Fomin, {Fedor V.} and {van 't Hof}, Pim and Dani{\"e}l Paulusma",
note = "eemcs-eprint-21076",
year = "2013",
doi = "10.1007/s00453-011-9576-4",
language = "Undefined",
volume = "65",
pages = "129--145",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer",
number = "1",

}

Exact algorithms for finding longest cycles in claw-free graphs. / Broersma, Haitze J.; Fomin, Fedor V.; van 't Hof, Pim; Paulusma, Daniël.

In: Algorithmica, Vol. 65, No. 1, 2013, p. 129-145.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Broersma, Haitze J.

AU - Fomin, Fedor V.

AU - van 't Hof, Pim

AU - Paulusma, Daniël

N1 - eemcs-eprint-21076

PY - 2013

Y1 - 2013

N2 - 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 (n) time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses (1657n) 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 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 deterministic algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses (16818n) time and exponential space, and one algorithm that uses (18878n) time and polynomial space.

AB - 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 (n) time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses (1657n) 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 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 deterministic algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses (16818n) time and exponential space, and one algorithm that uses (18878n) time and polynomial space.

KW - EWI-21076

KW - MSC-05C

KW - (Hamilton) cycle

KW - Exact algorithm

KW - IR-86129

KW - NP-complete

KW - NP-hard

KW - Hamiltonian graph

KW - METIS-297586

KW - Computational Complexity

U2 - 10.1007/s00453-011-9576-4

DO - 10.1007/s00453-011-9576-4

M3 - Article

VL - 65

SP - 129

EP - 145

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 1

ER -