Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

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.
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 Thilikos <>
Soumis le : lundi 22 janvier 2018 - 08:38:40
Dernière modification le : jeudi 26 novembre 2020 - 15:50:03
Archivage à long terme le : : jeudi 24 mai 2018 - 07:42:26

Fichier

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

Identifiants

Collections

Citation

Petr A. 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

370

Téléchargements de fichiers

237