The parameterized complexity of graph cyclability

Petr A. Golovach, Marcin Kamiński, Spyridon Maniatis, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

The cyclability of a graph is the maximum integer k for which every k vertices lie on a cycle. The algorithmic version of the problem, given a graph G and a nonnegative integer k, decide whether the cyclability of G is at least k, is NP-hard. We study the parametrized complexity of this problem. We prove that this problem, parameterized by k, is co-W[1]-hard and that it does not admit a polynomial kernel on planar graphs, unless NP ⊆ co-NP/poly. On the positive side, we give an FPT algorithm for planar graphs that runs in time 22O(k2log k) • n2. Our algorithm is based on a series of graph-theoretical results on cyclic linkages in planar graphs.

Original languageEnglish (US)
Pages (from-to)511-541
Number of pages31
JournalSIAM Journal on Discrete Mathematics
Volume31
Issue number1
DOIs
StatePublished - 2017

Keywords

  • Cyclability
  • Linkages
  • Parameterized complexity
  • Treewidth

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'The parameterized complexity of graph cyclability'. Together they form a unique fingerprint.

Cite this