# Cutwidth: obstructions and algorithmic aspects

3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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)}$. For our proof, we introduce the concept of a lean ordering that can be seen as the analogue of lean decompositions defined by Thomas in [A Menger-like property of tree-width: The finite case, J. Comb. Theory, Ser. B, 48(1):67--76, 1990] for the case of treewidth. 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)}\cdot 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, Bodlaender, and Serna in [Cutwidth I: A linear time fixed parameter algorithm, J. Algorithms, 56(1):1--24, 2005] and [Cutwidth II: Algorithms for partial $w$-trees of bounded degree, 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.
Keywords :
Type de document :
Communication dans un congrès
IPEC: International symposium on Parameterized and Exact Computation, Aug 2016, Aarhus, Denmark. 11th International Symposium on Parameterized and Exact Computation, LIPIcs (63), pp.15:1--15:13, 2017, 〈http://conferences.au.dk/algo16/ipec/〉. 〈10.4230/LIPIcs.IPEC.2016.15〉

Littérature citée [23 références]

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01370305
Contributeur : Dimitrios M. Thilikos <>
Soumis le : jeudi 22 septembre 2016 - 12:47:40
Dernière modification le : jeudi 15 novembre 2018 - 18:34:07

### Fichier

cut_obs_ArXiV.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna. Cutwidth: obstructions and algorithmic aspects. IPEC: International symposium on Parameterized and Exact Computation, Aug 2016, Aarhus, Denmark. 11th International Symposium on Parameterized and Exact Computation, LIPIcs (63), pp.15:1--15:13, 2017, 〈http://conferences.au.dk/algo16/ipec/〉. 〈10.4230/LIPIcs.IPEC.2016.15〉. 〈lirmm-01370305〉

### Métriques

Consultations de la notice

## 210

Téléchargements de fichiers