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.MFCS.2016.75
URN: urn:nbn:de:0030-drops-64846
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6484/
Kolay, Sudeshna ;
Panolan, Fahad ;
Raman, Venkatesh ;
Saurabh, Saket
Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs
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 r-colourable graphs (when l=0) and hence not surprisingly, determining whether a given graph is an (r,l)-graph is NP-hard even when r >= 3 or l >= 3 in general graphs.
When r and ell are part of the input, then the recognition problem is NP-hard 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 fixed-parameter 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 NP-hard 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:1--75:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-016-3},
ISSN = {1868-8969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6484},
URN = {urn:nbn:de:0030-drops-64846},
doi = {10.4230/LIPIcs.MFCS.2016.75},
annote = {Keywords: graph deletion, FPT algorithms, polynomial kernels}
}
|
Keywords: |
|
graph deletion, FPT algorithms, polynomial kernels |
|
Collection: |
|
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
19.08.2016 |
