Cygan, Marek, Lokshtanov, Daniel, Pilipczuk, Marcin, Pilipczuk, Michał and Saurabh, Saket (2014) On the hardness of losing width. Theory of Computing Systems, Volume 54 (Number 1). pp. 73-82. doi:10.1007/s00224-013-9480-1

Research output not available from this repository, contact author.

Request Changes to record.

Abstract

Let η≥0 be an integer and G be a graph. A set X⊆V(G) is called a η-treewidth modulator in G if G∖X has treewidth at most η. Note that a 0-treewidth modulator is a vertex cover, while a 1-treewidth modulator is a feedback vertex set of G. In the η/ρ-Treewidth Modulator problem we are given an undirected graph G, a ρ-treewidth modulator X⊆V(G) in G, and an integer ℓ and the objective is to determine whether there exists an η-treewidth modulator Z⊆V(G) in G of size at most ℓ. In this paper we study the kernelization complexity of η/ρ-Treewidth Modulator parameterized by the size of X. We show that for every fixed η and ρ that either satisfy 1≤η<ρ, or η=0 and 2≤ρ, the η/ρ-Treewidth Modulator problem does not admit a polynomial kernel unless NP⊆coNP/poly. This resolves an open problem raised by Bodlaender and Jansen (STACS, pp. 177–188, 2011). Finally, we complement our kernelization lower bounds by showing that ρ/0-Treewidth Modulator admits a polynomial kernel for any fixed ρ.

Item Type:	Journal Article
Divisions:	Faculty of Science > Computer Science
Journal or Publication Title:	Theory of Computing Systems
Publisher:	Springer New York LLC
ISSN:	1432-4350
Official Date:	1 January 2014
Dates:	Date Event 1 January 2014 Published
Volume:	Volume 54
Number:	Number 1
Page Range:	pp. 73-82
DOI:	10.1007/s00224-013-9480-1
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Embodied As:	1

Request changes or add full text files to a record

Repository staff actions (login required)

View Item