Lossy Kernels for Hitting Subgraphs
Lossy Kernels for Hitting Subgraphs
复制标题
用于命中子图的有损内核
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Ramanujan
中科院分区：
文献类型：
--
作者：
E. Eiben;D. Hermelin;M. Ramanujan
本文从Lokshtanov等人最近提出的近似核化框架出发，研究了连通H-命中集和支配集问题。[STEC 2017]。对于连通H-碰集问题，我们得到了每个α>；1的一个α-近似核，并用自然加权形式的一个下界来补充它。然后，我们对d-退化图上支配集问题的近似因子和核大小之间的权衡进行了精细的分析，并给出了大小固定的已知d^2-近似核和大小为k^{O(d^2)}的1-近似核之间的近似核的内插.
In this paper, we study the Connected H-hitting Set and Dominating Set problems from the perspective of approximate kernelization, a framework recently introduced by Lokshtanov et al. [STOC 2017]. For the Connected H-hitting set problem, we obtain an alpha-approximate kernel for every alpha>1 and complement it with a lower bound for the natural weighted version. We then perform a refined analysis of the tradeoff between the approximation factor and kernel size for the Dominating Set problem on d-degenerate graphs and provide an interpolation of approximate kernels between the known d^2-approximate kernel of constant size and 1-approximate kernel of size k^{O(d^2)}.