An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set

Abstract

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).

19 pages, 1 figures. Preliminary version appeared in Proceedings of WG-2022