Cutwidth: Obstructions and algorithmic aspects

Archontia C. Giannopoulou, Michał Pilipczuk, Jean Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication11th International Symposium on Parameterized and Exact Computation, IPEC 2016
EditorsJiong Guo, Danny Hermelin
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770231
StatePublished - Feb 1 2017
Event11th International Symposium on Parameterized and Exact Computation, IPEC 2016 - Aarhus, Denmark
Duration: Aug 24 2016Aug 26 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference11th International Symposium on Parameterized and Exact Computation, IPEC 2016


  • Cutwidth
  • Fixed-parameter tractability
  • Immersions
  • Obstructions

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Cutwidth: Obstructions and algorithmic aspects'. Together they form a unique fingerprint.

Cite this