An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion
Kanté, Mamadou Moustapha; Kim, Eun Jung; Kwon, O-joung; Paul, Christophe (2017), An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion, Algorithmica, 79, 1, p. 66–95. 10.1007/s00453-016-0230-z
Type
Article accepté pour publication ou publiéLien vers un document non conservé dans cette base
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01692676Date
2017Nom de la revue
AlgorithmicaVolume
79Numéro
1Éditeur
Springer
Pages
66–95
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Kanté, Mamadou Moustapha
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Kwon, O-joung
Paul, Christophe
Résumé (EN)
Linear rankwidth is a linearized variant of rankwidth, introduced by Oum and Seymour (J Comb Theory Ser B 96(4):514–528, 2006). Motivated from recent development on graph modification problems regarding classes of graphs of bounded treewidth or pathwidth, we study the LINEAR RANKWIDTH-1 VERTEX DELETION problem (shortly, LRW1-VERTEX DELETION). In the LRW1-VERTEX DELETION problem, given an n-vertex graph G and a positive integer k, we want to decide whether there is a set of at most k vertices whose removal turns G into a graph of linear rankwidth at most 1 and find such a vertex set if one exists. While the meta-theorem of Courcelle, Makowsky, and Rotics implies that LRW1-VERTEX DELETION can be solved in time f(k)⋅n3 for some function f, it is not clear whether this problem allows a running time with a modest exponential function. We first establish that LRW1-VERTEX DELETION can be solved in time 8k⋅nO(1). The major obstacle to this end is how to handle a long induced cycle as an obstruction. To fix this issue, we define necklace graphs and investigate their structural properties. Later, we reduce the polynomial factor by refining the trivial branching step based on a cliquewidth expression of a graph, and obtain an algorithm that runs in time 2O(k)⋅n4. We also prove that the running time cannot be improved to 2o(k)⋅nO(1) under the Exponential Time Hypothesis assumption. Lastly, we show that the LRW1-VERTEX DELETION problem admits a polynomial kernel.Mots-clés
Necklace graph; Thread graph; Cliquewidth; Rankwidth; Linear rankwidthPublications associées
Affichage des éléments liés par titre et auteur.
-
Paul, Christophe; Kim, Eun Jung; Kanté, Mamadou Moustapha; Kwon, O-joung (2015) Communication / Conférence
-
Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi (2016) Article accepté pour publication ou publié
-
Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau Valls, Ignasi; Sikdar, Somnath (2013-07) Communication / Conférence
-
Philip, Geevarghese; Paul, Christophe; Kim, Eun Jung (2015) Article accepté pour publication ou publié
-
Kim, Eun Jung; Oum, Sang-il; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2018) Article accepté pour publication ou publié