The Parameterized Complexity of Graph Cyclability

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 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 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.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2017, 31 (1), pp.511 - 541. 〈10.1137/141000014〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.umontpellier.fr/hal-01632332
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 22 janvier 2018 - 08:38:40
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : jeudi 24 mai 2018 - 07:42:26

Fichier

1412.3955.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Petr Golovach, Marcin Kamiński, Spyridon Maniatis, Dimitrios M. Thilikos. The Parameterized Complexity of Graph Cyclability. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2017, 31 (1), pp.511 - 541. 〈10.1137/141000014〉. 〈hal-01632332〉

Partager

Métriques

Consultations de la notice

118

Téléchargements de fichiers

27