Hols, EvaMaria 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 polynomialtime algorithm that, when given access to an oracle that outputs capproximate solutions in 𝒪(1) time, obtains an α ⋅ capproximate 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, EdgeDisjoint 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 VertexDisjoint Hpacking for connected graphs H, Clique Cover, Feedback Vertex Set and Edge Dominating Set.
BibTeX  Entry
@InProceedings{hols_et_al:LIPIcs:2020:12926,
author = {EvaMaria 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:160:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12926},
URN = {urn:nbn:de:0030drops129261},
doi = {10.4230/LIPIcs.ESA.2020.60},
annote = {Keywords: Approximation, Turing kernelization, Graph problems, Treewidth}
}
26.08.2020
Keywords: 

Approximation, Turing kernelization, Graph problems, Treewidth 
Seminar: 

28th Annual European Symposium on Algorithms (ESA 2020)

Issue date: 

2020 
Date of publication: 

26.08.2020 