论文标题
通过树宽参数参数的问题的近似Turing内核化
Approximate Turing Kernelization for Problems Parameterized by Treewidth
论文作者
论文摘要
我们扩展了Lokshtanov等人引入的有损核化的概念。 [STOC 2017]，以近似图灵内核。用于参数化优化问题的$α$ - 适应性的图灵内核是一种多项式时间算法，当给予访问$ o（1）$时间以$ o o（1）$时间输出的甲骨文的访问权限时，获得了$（α\ cdot c）$ - 使用$ $ $ f的$ f in of of of fif的$ o（cdot c）$（a）$（$ 范围。 使用此定义，我们表明，由树宽$ \ ell $参数化的独立集具有$（1+ \ varepsilon）$ - 带有$ o（\ frac {\ ell^2} {\ ell^2} {\ varepsilon}）$ Vertices $ Vertices的近似图灵内核，回答了Lokshtanov等人的开放问题。 [Stoc 2017]。此外，我们给出$（1+ \ varepsilon）$ - 以下图形问题的近似图灵内核，以下图形问题：顶部封面，边缘封面，边缘封面，边缘 - 边界三角形三角形包装和连接的顶点盖。 我们通过证明我们称为“友好”的所有图形问题允许$（1+ \ varepsilon）$ - 近似多项式大小的图灵内核来概括为独立集和顶点盖的结果。我们使用它来获得近似的Turing内核，用于顶点disexhient $ h $ - 包装连接图$ h $，集团盖，反馈顶点集和边缘统治集。
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 $O(1)$ time, obtains an $(α\cdot 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 $\ell$ has a $(1+\varepsilon)$-approximate Turing kernel with $O(\frac{\ell^2}{\varepsilon})$ vertices, answering an open question posed by Lokshtanov et al. [STOC 2017]. Furthermore, we give $(1+\varepsilon)$-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+\varepsilon)$-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.
