2026-07-22T04:18:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6930 2024-03-06T10:38:48Z ddc:004 open_access

Cutwidth: Obstructions and Algorithmic Aspects Giannopoulou, Archontia C. Pilipczuk, Michal Raymond, Jean-Florent Thilikos, Dimitrios M. Wrochna, Marcin cutwidth obstructions immersions fixed-parameter tractability 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 2^O(k^3*log(k)). As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time 2^O(k^2*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 [J. Algorithms 2005], our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Archontia C. Giannopoulou and Michal Pilipczuk and Jean-Florent Raymond and Dimitrios M. Thilikos and Marcin Wrochna 2017 Is Part Of LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2016.15 urn:nbn:de:0030-drops-69306 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.15 eng https://creativecommons.org/licenses/by/3.0/legalcode