On the Lossy Kernelization for Connected Treedepth Deletion Set

Eduard Eiben; Diptapriyo Majumdar; M. S.  Ramanujan

doi:10.1007/978-3-031-15914-5_15

On the Lossy Kernelization for Connected Treedepth Deletion Set

Eduard Eiben, Diptapriyo Majumdar, M. S. Ramanujan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	48th International Workshop, WG 2022
Editors	Michael A. Bekos, Michael Kaufmann
Publisher	Springer
Pages	201-214
Number of pages	14
ISBN (Electronic)	978-3-031-15914-5
ISBN (Print)	978-3-031-15913-8
DOIs	https://doi.org/10.1007/978-3-031-15914-5_15
Publication status	Published - 1 Oct 2022

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	13453

Access to Document

10.1007/978-3-031-15914-5_15

Cite this

@inproceedings{5591c7128f8745d2a3e96e85bde622f2,

title = "On the Lossy Kernelization for Connected Treedepth Deletion Set",

abstract = "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",

author = "Eduard Eiben and Diptapriyo Majumdar and Ramanujan, \{M. S.\}",

year = "2022",

month = oct,

day = "1",

doi = "10.1007/978-3-031-15914-5\_15",

language = "English",

isbn = "978-3-031-15913-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "201--214",

editor = "Bekos, \{Michael A.\} and Michael Kaufmann",

booktitle = "Graph-Theoretic Concepts in Computer Science",

}

On the Lossy Kernelization for Connected Treedepth Deletion Set. / Eiben, Eduard; Majumdar, Diptapriyo; Ramanujan, M. S. .
Graph-Theoretic Concepts in Computer Science: 48th International Workshop, WG 2022. ed. / Michael A. Bekos; Michael Kaufmann. Springer, 2022. p. 201-214 (Lecture Notes in Computer Science; Vol. 13453).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On the Lossy Kernelization for Connected Treedepth Deletion Set

AU - Eiben, Eduard

AU - Majumdar, Diptapriyo

AU - Ramanujan, M. S.

PY - 2022/10/1

Y1 - 2022/10/1

N2 - 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

AB - 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

U2 - 10.1007/978-3-031-15914-5_15

DO - 10.1007/978-3-031-15914-5_15

M3 - Conference contribution

SN - 978-3-031-15913-8

T3 - Lecture Notes in Computer Science

SP - 201

EP - 214

BT - Graph-Theoretic Concepts in Computer Science

A2 - Bekos, Michael A.

A2 - Kaufmann, Michael

PB - Springer

ER -