The Library
On cutwidth parameterized by vertex cover
Tools
Tools
Tools
Cygan, Marek, Lokshtanov, Daniel, Pilipczuk, Marcin, Pilipczuk, Michał and Saurabh, Saket (2014) On cutwidth parameterized by vertex cover. Algorithmica, Volume 68 (Number 4). pp. 940-953. doi:10.1007/s00453-012-9707-6 ISSN 0178-4617.
|
PDF (Creative Commons : Attribution 4.0)
WRAP_art%3A10.1007%2Fs00453-012-9707-6.pdf - Published Version - Requires a PDF viewer. Download (719Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s00453-012-9707-6
Abstract
We study the Cutwidth problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for Cutwidth with running time O(2 k n O(1)). Here k is the size of a minimum vertex cover of the input graph G, and n is the number of vertices in G. Our algorithm gives an O(2 n/2 n O(1)) time algorithm for Cutwidth on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for Cutwidth on a graph class where the problem remains NP-complete. Additionally, we show that Cutwidth parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless NP⊆coNP/poly. Our kernelization lower bound contrasts with the recent results of Bodlaender et al. (ICALP, Springer, Berlin, 2011; SWAT, Springer, Berlin, 2012) that both Treewidth and Pathwidth parameterized by vertex cover do admit polynomial kernels.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Parameter estimation, Computational complexity, Computer algorithms | ||||
| Journal or Publication Title: | Algorithmica | ||||
| Publisher: | Springer Verlag | ||||
| ISSN: | 0178-4617 | ||||
| Official Date: | 1 April 2014 | ||||
| Dates: |
|
||||
| Volume: | Volume 68 | ||||
| Number: | Number 4 | ||||
| Page Range: | pp. 940-953 | ||||
| DOI: | 10.1007/s00453-012-9707-6 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||
| Date of first compliant deposit: | 28 December 2015 | ||||
| Date of first compliant Open Access: | 28 December 2015 | ||||
| Embodied As: | 1 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
