Name
Abstract | ||
|---|---|---|
We study the Cutwidth problem, where 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(2knO(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(2n/2nO(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 the recent result of Bodlaender et al.[ICALP 2011] that Treewidth parameterized by vertex cover does admit a polynomial kernel. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-642-28050-4_20 | Algorithmica |
Keywords | DocType | Volume |
Cutwidth,Vertex cover parameterization,Parameterized complexity,Composition algorithms,Polynomial kernel | Journal | 68 |
Issue | Citations | PageRank |
4 | 4 | 0.41 |
References | Authors | |
21 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marek Cygan | 1 | 556 | 40.52 |
| Daniel Lokshtanov | 2 | 1438 | 110.05 |
| Marcin Pilipczuk | 3 | 436 | 47.86 |
| michal pilipczuk | 4 | 403 | 51.93 |
| Saket Saurabh | 5 | 2023 | 179.50 |