Parameterized K_4-Cover in Single Exponential Time

Eunjung Kim 1 Christophe Paul 1 Geevarghese Philip 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 IMSc - Institute of Mathematical Sciences [India]
Abstract : Given an input graph G on n vertices and an integer k, the parameterized K4-minor cover problem asks whether there is a set S of at most k vertices whose deletion results in a K4-minor free graph or, equivalently, in a graph of treewidth at most 2. The problem can thus also be called Treewidth-2 Vertex Deletion. This problem is inspired by two well-studied parameterized vertex deletion problems, Vertex Cover and Feedback Vertex Set, which can be expressed as Treewidth-t Vertex Deletion problems: t = 0 for Vertex Cover and t = 1 for Feedback Vertex Set. While a single-exponential FPT algorithm has been known for a long time for Vertex Cover, such an algorithm for Feedback Vertex Set was devised comparatively recently. While it is known to be unlikely that Treewidth-t Vertex Deletion can be solved in time $c^{o(k)} * n^{O(1)}$, it was open whether the K4-minor cover could be solved in single-exponential FPT time, i.e. in $c^k * n^{O(1)}$ time. This paper answers this question in the affirmative
Type de document :
Communication dans un congrès
SWAT: Scandinavian Workshop on Algorithmic Theory, Jul 2012, Helsinki, Sweden. 13th Scandinavian Symposium and Workshops on Algorithm Theory, LNCS (7357), pp.199-130, 2012
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00805191
Contributeur : Christophe Paul <>
Soumis le : mercredi 27 mars 2013 - 12:43:27
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00805191, version 1

Collections

ALGCO | LIRMM | MIPS | TDS-MACS | UNIV-MONTPELLIER

Citation

Eunjung Kim, Christophe Paul, Geevarghese Philip. Parameterized K_4-Cover in Single Exponential Time. SWAT: Scandinavian Workshop on Algorithmic Theory, Jul 2012, Helsinki, Sweden. 13th Scandinavian Symposium and Workshops on Algorithm Theory, LNCS (7357), pp.199-130, 2012. 〈lirmm-00805191〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

83

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD