The Parameterized Complexity of Graph Cyclability
Petr A. Golovach, Marcin Kamiński, Spyridon Maniatis, Dimitrios M. Thilikos · Lecture notes in computer science · 2014
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 ${\sf co{-}W[1]}$-hard and that it does not admit a polynomial kernel on planar graphs, unless ${NP}\subseteq{\sf co}{-}{NP}/{poly}$. On the positive side, we give an FPT algorithm for planar graphs that runs in time $2^{2^{O(k^2\log k)}}\cdot n^2$. Our algorithm is based on a series of graph-theoretical results on cyclic linkages in planar graphs.