Kanté, Mamadou Moustapha ;
Kim, Eun Jung ;
Kwon, Ojoung ;
Paul, Christophe
An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth1 Vertex Deletion
Abstract
Linear rankwidth is a linearized variant of rankwidth, introduced by Oum and Seymour [Approximating cliquewidth and branchwidth. J. Combin. Theory Ser. B, 96(4):514528, 2006.], and it is similar to pathwidth, which is the linearized variant of treewidth. Motivated from the results on graph modification problems into graphs of bounded treewidth or pathwidth, we investigate a graph modification problem into the class of graphs having linear rankwidth at most one, called the Linear Rankwidth1 Vertex Deletion (shortly, LRW1Vertex Deletion). In this problem, given an nvertex 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 one and if one exists, find such a vertex set. While the metatheorem of Courcelle, Makowsky, and Rotics implies thatLRW1Vertex Deletion can be solved in time f(k) * n^3 for some function f, it is not clear whether this problem allows a runtime with a modest exponential function. We establish that LRW1Vertex Deletion can be solved in time 8^k * n^{O(1)}. The major obstacle to this end is how to handle a long induced cycle as an obstruction. To fix this issue, we define the necklace graphs and investigate their structural properties.
We also show that the LRW1Vertex Deletion has a polynomial kernel.
BibTeX  Entry
@InProceedings{kant_et_al:LIPIcs:2015:5578,
author = {Mamadou Moustapha Kant{\'e} and Eun Jung Kim and Ojoung Kwon and Christophe Paul},
title = {{An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth1 Vertex Deletion}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {138150},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897927},
ISSN = {18688969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5578},
URN = {urn:nbn:de:0030drops55788},
doi = {10.4230/LIPIcs.IPEC.2015.138},
annote = {Keywords: (linear) rankwidth, distancehereditary graphs, thread graphs, parameterized complexity, kernelization}
}
2015
Keywords: 

(linear) rankwidth, distancehereditary graphs, thread graphs, parameterized complexity, kernelization 
Seminar: 

10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Issue date: 

2015 
Date of publication: 

2015 