























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).
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。