论文标题
连接的TreeDeppth删除集的提高时间效率的近似内核化
An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set
论文作者
论文摘要
我们研究了连接的η-treeDeptth缺失问题，其中输入实例是一个未空的图G =（V，e）和整数k。目的是确定在大多数k顶点的g具有S \ subseteq v（g），以使g -s最多具有ηandg [s]。由于此问题自然会概括众所周知的连接顶点覆盖物，当通过解决方案尺寸K参数化时，除非NP \ subseteq conp/poly，否则连接的η-treeDeppth删除不会吸收多项式内核。这激发了我们为此问题设计多项式大小的近似内核。在本文中，我们表明，每次0 <ε<= 1，连接的η-treeDepth删除套件允许a（1+ε） - approximate内核，带有O（k^{2^{η+ 1/ε}}）顶点，即一个多物质大小的近似近近近核心方案（psaks）。
We study the CONNECTED η-TREEDEPTH DELETION problem where the input instance is an undireted graph G = (V, E) and an integer k. The objective is to decide if G has a set S \subseteq V(G) of at most k vertices such that G - S has treedepth at most ηand G[S] is connected. As this problem naturally generalizes the well-known CONNECTED VERTEX COVER, when parameterized by solution size k, the CONNECTED η-TREEDEPTH DELETION does not admit polynomial kernel unless NP \subseteq coNP/poly. This motivates us to design an approximate kernel of polynomial size for this problem. In this paper, we show that for every 0 < ε<= 1, CONNECTED η-TREEDEPTH DELETION SET admits a (1+ε)-approximate kernel with O(k^{2^{η+ 1/ε}}) vertices, i.e. a polynomial-sized approximate kernelization scheme (PSAKS).
