On the lossy kernelization for connected treedepth deletion set

We study the CONNECTED η -TREEDEPTH DELETION problem, where the input instance is an undirected graph G, and an integer k and the objective is to decide whether there is a vertex set S⊆V(G) such that |S|≤k, every connected component of G−S has treedepth at most η and G[S] is a connected graph. As this problem naturally generalizes the well-studied CONNECTED VERTEX COVER problem, when parameterized by the solution size k, CONNECTED η -TREEDEPTH DELETION is known to not admit a polynomial kernel unless NP⊆coNP/poly. This motivates the question of designing approximate polynomial kernels for this problem. In this paper, we show that for every fixed 0