TY - JOUR

T1 - Cutwidth

T2 - Obstructions and Algorithmic Aspects

AU - Giannopoulou, Archontia C.

AU - Pilipczuk, Michał

AU - Raymond, Jean Florent

AU - Thilikos, Dimitrios M.

AU - Wrochna, Marcin

N1 - Publisher Copyright:
© 2018, The Author(s).

PY - 2019/2/15

Y1 - 2019/2/15

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(k3logk). As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time 2O(k2logk)·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.

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(k3logk). As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time 2O(k2logk)·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.

KW - Cutwidth

KW - Fixed-parameter tractability

KW - Immersions

KW - Obstructions

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

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

U2 - 10.1007/s00453-018-0424-7

DO - 10.1007/s00453-018-0424-7

M3 - Article

AN - SCOPUS:85044092082

SN - 0178-4617

VL - 81

SP - 557

EP - 588

JO - Algorithmica

JF - Algorithmica

IS - 2

ER -