2022/12/01 by Eduard Eiben, Diptapriyo Majumdar, Eiben, Eduard +3
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2212.00418
openalex publication_date 2022/12/01 · openalex created_date 2022/12/13 · openalex updated_date 2026/07/28
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).