Cutwidth: Obstructions and Algorithmic Aspects

• Published in: Algorithmica 2019-02, Vol.81 (2), p.557-588
• Main Authors: Giannopoulou, Archontia C., Pilipczuk, Michał, Raymond, Jean-Florent, Thilikos, Dimitrios M., Wrochna, Marcin
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Apexes; Combinatorial analysis; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Algorithms; Data Structures and Information Theory; Design parameters; Discrete Mathematics; Graph theory; Graphs; Layouts; Mathematics of Computing; Obstructions; Submerging; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-018-0424-7

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, given by Thilikos et al. (J Algorithms 56(1):1–24, 2005 ; J Algorithms 56(1):25–49, 2005 ), our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts.