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.FSTTCS.2015.420
URN: urn:nbn:de:0030-drops-56456
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5645/
Go to the corresponding LIPIcs Volume Portal

Kolay, Sudeshna ; Panolan, Fahad

Parameterized Algorithms for Deletion to (r,ell)-Graphs

pdf-format:
30.pdf (0.5 MB)

Abstract

For fixed integers r,ell geq 0, a graph G is called an (r,ell)-graph if the vertex set V(G) can be partitioned into r independent sets and ell cliques. This brings us to the following natural parameterized questions: Vertex (r,ell)-Partization and Edge (r,ell)-Partization. An input to these problems consist of a graph G and a positive integer k and the objective is to decide whether there exists a set S subseteq V(G) (S subseteq E(G)) such that the deletion of S from G results in an (r,ell)-graph. These problems generalize well studied problems such as Odd Cycle Transversal, Edge Odd Cycle Transversal, Split Vertex Deletion and Split Edge Deletion. We do not hope to get parameterized algorithms for either Vertex (r, ell)-Partization or Edge (r,ell)-Partization when either of r or ell is at least 3 as the recognition problem itself is NP-complete. This leaves the case of r,ell in {1,2}. We almost complete the parameterized complexity dichotomy for these problems by obtaining the following results:
- We show that Vertex (r,ell)-Partization is fixed parameter tractable (FPT) for r,ell in {1,2}. Then we design an Oh(sqrt log n)-factor approximation algorithms for these problems. These approximation algorithms are then utilized to design polynomial sized randomized Turing kernels for these problems.
- Edge (r,ell)-Partization is FPT when (r,ell)in{(1,2),(2,1)}. However, the parameterized complexity of Edge (2,2)-Partization remains open.

For our approximation algorithms and thus for Turing kernels we use
an interesting finite forbidden induced graph characterization, for a class of graphs known as (r,ell)-split graphs, properly containing the class of (r,ell)-graphs. This approach to obtain approximation algorithms could be of an independent interest.

BibTeX - Entry

@InProceedings{kolay_et_al:LIPIcs:2015:5645,
  author =	{Sudeshna Kolay and Fahad Panolan},
  title =	{{Parameterized Algorithms for Deletion to (r,ell)-Graphs}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{420--433},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Prahladh Harsha and G. Ramalingam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5645},
  URN =		{urn:nbn:de:0030-drops-56456},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.420},
  annote =	{Keywords: FPT, Turing kernels, Approximation algorithms}
}

Keywords: FPT, Turing kernels, Approximation algorithms
Collection: 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Issue Date: 2015
Date of publication: 14.12.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI