## 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 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 ⊆ 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) • n^{2}. Our algorithm is based on a series of graph-theoretical results on cyclic linkages in planar graphs.

Original language | English (US) |
---|---|

Pages (from-to) | 511-541 |

Number of pages | 31 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 31 |

Issue number | 1 |

DOIs | |

State | Published - 2017 |

## Keywords

- Cyclability
- Linkages
- Parameterized complexity
- Treewidth

## ASJC Scopus subject areas

- General Mathematics