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.ESA.2020.60
URN: urn:nbn:de:0030-drops-129261
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12926/
Hols, Eva-Maria C. ;
Kratsch, Stefan ;
Pieterse, Astrid
Approximate Turing Kernelization for Problems Parameterized by Treewidth
Abstract
We extend the notion of lossy kernelization, introduced by Lokshtanov et al. [STOC 2017], to approximate Turing kernelization. An α-approximate Turing kernel for a parameterized optimization problem is a polynomial-time algorithm that, when given access to an oracle that outputs c-approximate solutions in ?(1) time, obtains an α ⋅ c-approximate solution to the considered problem, using calls to the oracle of size at most f(k) for some function f that only depends on the parameter.
Using this definition, we show that Independent Set parameterized by treewidth ? has a (1+ε)-approximate Turing kernel with ?(?²/ε) vertices, answering an open question posed by Lokshtanov et al. [STOC 2017]. Furthermore, we give (1+ε)-approximate Turing kernels for the following graph problems parameterized by treewidth: Vertex Cover, Edge Clique Cover, Edge-Disjoint Triangle Packing and Connected Vertex Cover.
We generalize the result for Independent Set and Vertex Cover, by showing that all graph problems that we will call friendly admit (1+ε)-approximate Turing kernels of polynomial size when parameterized by treewidth. We use this to obtain approximate Turing kernels for Vertex-Disjoint H-packing for connected graphs H, Clique Cover, Feedback Vertex Set and Edge Dominating Set.
BibTeX - Entry
@InProceedings{hols_et_al:LIPIcs:2020:12926,
author = {Eva-Maria C. Hols and Stefan Kratsch and Astrid Pieterse},
title = {{Approximate Turing Kernelization for Problems Parameterized by Treewidth}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {60:1--60:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-162-7},
ISSN = {1868-8969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12926},
URN = {urn:nbn:de:0030-drops-129261},
doi = {10.4230/LIPIcs.ESA.2020.60},
annote = {Keywords: Approximation, Turing kernelization, Graph problems, Treewidth}
}
|
Keywords: |
|
Approximation, Turing kernelization, Graph problems, Treewidth |
|
Collection: |
|
28th Annual European Symposium on Algorithms (ESA 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
26.08.2020 |
