Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Kanté, Mamadou Moustapha; Kim, Eun Jung; Kwon, O-joung; Paul, Christophe http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-55788
URL:

; ; ;

An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion

pdf-format:


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
Seminar: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue date: 2015
Date of publication: 2015


DROPS-Home | Fulltext Search | Imprint Published by LZI