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.2016.23
URN: urn:nbn:de:0030-drops-68587
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6858/
Go to the corresponding LIPIcs Volume Portal

Krithika, R. ; Misra, Pranabendu ; Rai, Ashutosh ; Tale, Prafullkumar

Lossy Kernels for Graph Contraction Problems

pdf-format:
LIPIcs-FSTTCS-2016-23.pdf (0.5 MB)

Abstract

We study some well-known 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 c-approximate 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 alpha-approximate kernel for every approximation parameter alpha > 1. In this work, we design PSAKSs for Tree Contraction, Star Contraction, Out-Tree 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:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6858},
  URN =		{urn:nbn:de:0030-drops-68587},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.23},
  annote =	{Keywords: parameterized complexity, lossy kernelization, graph theory, edge contraction problems}
}

Keywords: parameterized complexity, lossy kernelization, graph theory, edge contraction problems
Collection: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 10.12.2016

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