文章基本信息

标题：Approximate Turing Kernelization for Problems Parameterized by Treewidth
本地全文：下载
作者：Eva-Maria C. Hols ; Stefan Kratsch ; Astrid Pieterse 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：60:1-60:23
DOI：10.4230/LIPIcs.ESA.2020.60
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Approximation; Turing kernelization; Graph problems; Treewidth