TY - GEN

T1 - Cutwidth

T2 - 11th International Symposium on Parameterized and Exact Computation, IPEC 2016

AU - Giannopoulou, Archontia C.

AU - Pilipczuk, Michał

AU - Raymond, Jean Florent

AU - Thilikos, Dimitrios M.

AU - Wrochna, Marcin

N1 - Publisher Copyright:
© 2016 Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna.

PY - 2017/2/1

Y1 - 2017/2/1

N2 - Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most k. We prove that every minimal immersion obstruction for cutwidth at most k has size at most 2O(k3log k). As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time 2O(k2 log k) · n, where k is the optimum width and n is the number of vertices. While being slower by a log k-factor in the exponent than the fastest known algorithm, due to Thilikos, Bodlaender, and Serna [17, 18], our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts.

AB - Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most k. We prove that every minimal immersion obstruction for cutwidth at most k has size at most 2O(k3log k). As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time 2O(k2 log k) · n, where k is the optimum width and n is the number of vertices. While being slower by a log k-factor in the exponent than the fastest known algorithm, due to Thilikos, Bodlaender, and Serna [17, 18], our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts.

KW - Cutwidth

KW - Fixed-parameter tractability

KW - Immersions

KW - Obstructions

UR - http://www.scopus.com/inward/record.url?scp=85014591376&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85014591376&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.IPEC.2016.15

DO - 10.4230/LIPIcs.IPEC.2016.15

M3 - Conference contribution

AN - SCOPUS:85014591376

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 11th International Symposium on Parameterized and Exact Computation, IPEC 2016

A2 - Guo, Jiong

A2 - Hermelin, Danny

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 24 August 2016 through 26 August 2016

ER -