On the Lossy Kernelization for Connected Treedepth Deletion Set

Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication48th International Workshop, WG 2022
EditorsMichael A. Bekos, Michael Kaufmann
Number of pages14
ISBN (Electronic)978-3-031-15914-5
ISBN (Print)978-3-031-15913-8
Publication statusPublished - 1 Oct 2022

Publication series

NameLecture Notes in Computer Science

Cite this