THE PARAMETERIZED COMPLEXITY OF GRAPH CYCLABILITY

摘要

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 co-W[1]-hard and that it does not admit a polynomial kernel on planar graphs, unless NP subset of co-NP/poly. On the positive side, we give an F P T algorithm for planar graphs that runs in time 2(2O) (k(2) (logk)).n(2). Our algorithm is based on a series of graph- theoretical results on cyclic linkages in planar graphs.