The Library
On the lossy kernelization for connected treedepth deletion set
Tools
Eiben, Eduard, Majumdar, Diptapriyo and Ramanujan, M. S. (2022) On the lossy kernelization for connected treedepth deletion set. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022), Tübingen, Germany, 22-24 Jun 2022. Published in: Graph-Theoretic Concepts in Computer Science, 13453 pp. 201-214. ISBN 9783031159138. doi:10.1007/978-3-031-15914-5_15 ISSN 1611-3349.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: https://doi.org/10.1007/978-3-031-15914-5_15
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<ε≤1, CONNECTED η -TREEDEPTH DELETION admits a time-efficient (1+ε)-approximate kernel of size k2O(η+1/ε) (i.e., a Polynomial-size Approximate Kernelization Scheme).
Item Type: | Conference Item (Paper) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
SWORD Depositor: | Library Publications Router | |||||||||
Series Name: | Lecture Notes in Computer Science | |||||||||
Journal or Publication Title: | Graph-Theoretic Concepts in Computer Science | |||||||||
Publisher: | Springer International Publishing | |||||||||
ISBN: | 9783031159138 | |||||||||
ISSN: | 1611-3349 | |||||||||
Official Date: | 1 October 2022 | |||||||||
Dates: |
|
|||||||||
Volume: | 13453 | |||||||||
Page Range: | pp. 201-214 | |||||||||
DOI: | 10.1007/978-3-031-15914-5_15 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Conference Paper Type: | Paper | |||||||||
Title of Event: | International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022) | |||||||||
Type of Event: | Workshop | |||||||||
Location of Event: | Tübingen, Germany | |||||||||
Date(s) of Event: | 22-24 Jun 2022 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |