Krithika, R. ;
Misra, Pranabendu ;
Rai, Ashutosh ;
Tale, Prafullkumar
Lossy Kernels for Graph Contraction Problems
Abstract
We study some wellknown graph contraction problems in the recently introduced framework of lossy kernelization. In classical kernelization, given an instance (I,k) of a parameterized problem, we are interested in obtaining (in polynomial time) an equivalent instance (I',k') of the same problem whose size is bounded by a function in k. This notion however has a major limitation. Given an approximate solution to the instance (I',k'), we can say nothing about the original instance (I,k). To handle this issue, among others, the framework of lossy kernelization was introduced. In this framework, for a constant alpha, given an instance (I,k) we obtain an instance (I',k') of the same problem such that, for every c>1, any capproximate solution to (I',k') can be turned into a (c*alpha)approximate solution to the original instance (I, k) in polynomial time. Naturally, we are interested in a polynomial time algorithm for this task, and further require that I' + k' = k^{O(1)}. Akin to the notion of polynomial time approximation schemes in approximation algorithms, a parameterized problem is said to admit a polynomial size approximate kernelization scheme (PSAKS) if it admits a polynomial size alphaapproximate kernel for every approximation parameter alpha > 1. In this work, we design PSAKSs for Tree Contraction, Star Contraction, OutTree Contraction and Cactus Contraction problems. These problems do not admit polynomial kernels, and we show that each of them admit a PSAKS with running time k^{f(alpha)}I^{O(1)} that returns an instance of size k^{g(alpha)} where f(alpha) and g(alpha) are constants depending on alpha.
BibTeX  Entry
@InProceedings{krithika_et_al:LIPIcs:2016:6858,
author = {R. Krithika and Pranabendu Misra and Ashutosh Rai and Prafullkumar Tale},
title = {{Lossy Kernels for Graph Contraction Problems}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {23:123:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770279},
ISSN = {18688969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6858},
URN = {urn:nbn:de:0030drops68587},
doi = {10.4230/LIPIcs.FSTTCS.2016.23},
annote = {Keywords: parameterized complexity, lossy kernelization, graph theory, edge contraction problems}
}
10.12.2016
Keywords: 

parameterized complexity, lossy kernelization, graph theory, edge contraction problems 
Seminar: 

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

Issue date: 

2016 
Date of publication: 

10.12.2016 