
The Library
On the hardness of losing width
Tools
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 ISSN 1432-4350.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s00224-013-9480-1
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, Engineering and Medicine > 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: |
|
||||
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 |