@article{3064197,
    title = "The parameterized complexity of graph cyclability",
    author = "Golovach, P.A. and Kamiński, M. and Maniatis, S. and Thilikos, D.M.",
    journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
    year = "2014",
    volume = "8737 LNCS",
    pages = "492-504",
    publisher = "Springer-Verlag",
    doi = "10.1007/978-3-662-44777-2_41",
    keywords = "Algorithms;  Graphic methods;  Polynomials, Cyclability;  FPT algorithms;  Graph G;  Nonnegative integers;  NP-hard;  Parameterized;  Parameterized complexity;  Planar graph, Graph theory",
    abstract = "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."
}