The Parameterized Complexity of Graph Cyclability - Université de Montpellier Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Discrete Mathematics Année : 2017

The Parameterized Complexity of Graph Cyclability

Résumé

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.
Fichier principal
Vignette du fichier
1412.3955.pdf (1.14 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01632332 , version 1 (22-01-2018)

Identifiants

Citer

Petr A. Golovach, Marcin Kamiński, Spyridon Maniatis, Dimitrios M. Thilikos. The Parameterized Complexity of Graph Cyclability. SIAM Journal on Discrete Mathematics, 2017, 31 (1), pp.511 - 541. ⟨10.1137/141000014⟩. ⟨hal-01632332⟩
233 Consultations
133 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More