The parameterized complexity of graph cyclability

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 non-negative integer k, decide whether the cyclability of G is at least k, is NP-hard. We prove that this problem, parameterized by k, is co-W[1]-hard. We give an FPT algorithm for planar graphs that runs in time 2 2O(k2 log k) · n2. Our algorithm is based on a series of graph theoretical results on cyclic linkages in planar graphs.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783662447765
StatePublished - 2014
Event22nd Annual European Symposium on Algorithms, ESA 2014 - Wroclaw, Poland
Duration: Sep 8 2014Sep 10 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8737 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other22nd Annual European Symposium on Algorithms, ESA 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this