License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.138
URN: urn:nbn:de:0030-drops-55788
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5578/
Kanté, Mamadou Moustapha ;
Kim, Eun Jung ;
Kwon, O-joung ;
Paul, Christophe
An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion
Abstract
Linear rankwidth is a linearized variant of rankwidth, introduced by Oum and Seymour [Approximating clique-width and branch-width. J. Combin. Theory Ser. B, 96(4):514-528, 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 Rankwidth-1 Vertex Deletion (shortly, LRW1-Vertex Deletion). In this 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 one and if one exists, find such a vertex set. While the meta-theorem of Courcelle, Makowsky, and Rotics implies thatLRW1-Vertex 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 LRW1-Vertex 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 LRW1-Vertex Deletion has a polynomial kernel.
BibTeX - Entry
@InProceedings{kant_et_al:LIPIcs:2015:5578,
author = {Mamadou Moustapha Kant{\'e} and Eun Jung Kim and O-joung Kwon and Christophe Paul},
title = {{An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {138--150},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-92-7},
ISSN = {1868-8969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5578},
URN = {urn:nbn:de:0030-drops-55788},
doi = {10.4230/LIPIcs.IPEC.2015.138},
annote = {Keywords: (linear) rankwidth, distance-hereditary graphs, thread graphs, parameterized complexity, kernelization}
}
|
Keywords: |
|
(linear) rankwidth, distance-hereditary graphs, thread graphs, parameterized complexity, kernelization |
|
Collection: |
|
10th International Symposium on Parameterized and Exact Computation (IPEC 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
19.11.2015 |
