TY - GEN

T1 - The parameterized complexity of graph cyclability

AU - Golovach, Petr A.

AU - Kamiński, Marcin

AU - Maniatis, Spyridon

AU - Thilikos, Dimitrios M.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84958526994&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958526994&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-44777-2_41

DO - 10.1007/978-3-662-44777-2_41

M3 - Conference contribution

AN - SCOPUS:84958526994

SN - 9783662447765

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 492

EP - 504

BT - Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings

PB - Springer Verlag

T2 - 22nd Annual European Symposium on Algorithms, ESA 2014

Y2 - 8 September 2014 through 10 September 2014

ER -