Abstract
For fixed integers r,l >= 0, a graph G is called an (r,l)graph if the vertex set V(G) can be partitioned into r independent sets and l cliques. Such a graph is also said to have cochromatic number r+l. The class of (r,l) graphs generalizes rcolourable graphs (when l=0) and hence not surprisingly, determining whether a given graph is an (r,l)graph is NPhard even when r >= 3 or l >= 3 in general graphs.
When r and ell are part of the input, then the recognition problem is NPhard even if the input graph is a perfect graph (where the Chromatic Number problem is solvable in polynomial time). It is also known to be fixedparameter tractable (FPT) on perfect graphs when parameterized by r and l. I.e. there is an f(r+l) n^O(1) algorithm on perfect graphs on n vertices where f is a function of r and l. Observe that such an algorithm is unlikely on general graphs as the problem is NPhard even for constant r and l.
In this paper, we consider the parameterized complexity of the following problem, which we call Vertex Partization. Given a perfect graph G and positive integers r,l,k decide whether there exists a set S subset or equal to V(G) of size at most k such that the deletion of S from G results in an (r,l)graph. This problem generalizes well studied problems such as Vertex Cover (when r=1 and l=0), Odd Cycle Transversal (when r=2, l=0) and Split Vertex Deletion (when r=1=l).
1. Vertex Partization on perfect graphs is FPT when parameterized by k+r+l.
2. The problem, when parameterized by k+r+l, does not admit any polynomial sized kernel, under standard complexity theoretic assumptions. In other words, in polynomial time, the input graph cannot be compressed to an equivalent instance of size polynomial in k+r+l. In fact, our result holds even when k=0.
3. When r,ell are universal constants, then Vertex Partization on perfect graphs, parameterized by k, has a polynomial sized kernel.
BibTeX  Entry
@InProceedings{kolay_et_al:LIPIcs:2016:6484,
author = {Sudeshna Kolay and Fahad Panolan and Venkatesh Raman and Saket Saurabh},
title = {{Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)Graphs}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {75:175:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6484},
URN = {urn:nbn:de:0030drops64846},
doi = {10.4230/LIPIcs.MFCS.2016.75},
annote = {Keywords: graph deletion, FPT algorithms, polynomial kernels}
}
Keywords: 

graph deletion, FPT algorithms, polynomial kernels 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) 
Issue Date: 

2016 
Date of publication: 

19.08.2016 