Kolay, Sudeshna ;
Panolan, Fahad
Parameterized Algorithms for Deletion to (r,ell)Graphs
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 NPcomplete. 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 = {420433},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897972},
ISSN = {18688969},
year = {2015},
volume = {45},
editor = {Prahladh Harsha and G. Ramalingam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5645},
URN = {urn:nbn:de:0030drops56456},
doi = {10.4230/LIPIcs.FSTTCS.2015.420},
annote = {Keywords: FPT, Turing kernels, Approximation algorithms}
}
2015
Keywords: 

FPT, Turing kernels, Approximation algorithms 
Seminar: 

35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Issue date: 

2015 
Date of publication: 

2015 