Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

On the hardness of losing width

Tools
- Tools
+ 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

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, 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:
DateEvent
1 January 2014Published
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us