An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set
An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set
复制标题
DOI：
10.48550/arxiv.2212.00418
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
E. Eiben;Diptapriyo Majumdar;M. Ramanujan
中科院分区：
文献类型：
--
作者：
E. Eiben;Diptapriyo Majumdar;M. Ramanujan
我们研究 CONNECTED eta-TREEDEPTH DELETION 问题，其中输入实例是无方向图 G = (V, E) 和整数 k。目标是确定 G 是否具有最多包含 k 个顶点的集合 S \subseteq V(G)，使得 G - S 的树深度最多为 eta 并且 G[S] 是连通的。由于这个问题自然地推广了众所周知的 CONNECTED VERTEX COVER，当通过解大小 k 参数化时，CONNECTED \eta-TREEDEPTH DELETION 不承认多项式内核，除非 NP \subseteq coNP/poly。这促使我们为这个问题设计一个多项式大小的近似核。在本文中，我们证明，对于每个 0<\epsilon<= 1，CONNECTED \eta-TREEDEPTH DELETION SET 承认具有 O(k^{2^{\eta + 1/\epsilon}}) 个顶点的 (1+\epsilon) 近似核，即多项式大小的近似核化方案（PSAKS）。
We study the CONNECTED \eta-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 \eta and G[S] is connected. As this problem naturally generalizes the well-known CONNECTED VERTEX COVER, when parameterized by solution size k, the CONNECTED \eta-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<\epsilon<= 1, CONNECTED \eta-TREEDEPTH DELETION SET admits a (1+\epsilon)-approximate kernel with O(k^{2^{\eta + 1/\epsilon}}) vertices, i.e. a polynomial-sized approximate kernelization scheme (PSAKS).