The Parameterized Complexity of Graph Cyclability

الأصل · EN

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 study the parametrized complexity of this problem. We prove that this problem, parameterized by k, is co-W[1]-hard and that its 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(k² k)· n². Our algorithm is based on a series of graph-theoretical results on cyclic linkages in planar graphs.