An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set
share
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 ⊆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 ⊆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).
READ FULL TEXT