TY - JOUR
TI - The parameterized complexity of graph cyclability
AU - Golovach, P.A.
AU - Kamiński, M.
AU - Maniatis, S.
AU - Thilikos, D.M.
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PY - 2014
VL - 8737 LNCS
TODO - null
SP - 492-504
PB - Springer-Verlag
SN - null
TODO - 10.1007/978-3-662-44777-2_41
TODO - Algorithms;  Graphic methods;  Polynomials, Cyclability;  FPT algorithms;  Graph G;  Nonnegative integers;  NP-hard;  Parameterized;  Parameterized complexity;  Planar graph, Graph theory
TODO - 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. © 2014 Springer-Verlag Berlin Heidelberg.
ER -