Giannopoulou, Archontia C. ;
Pilipczuk, Michal ;
Raymond, JeanFlorent ;
Thilikos, Dimitrios M. ;
Wrochna, Marcin
Cutwidth: Obstructions and Algorithmic Aspects
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)).
As an interesting algorithmic byproduct, we design a new fixedparameter 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 kfactor 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 selfcontained; arguably, it explains better the combinatorics of optimumwidth layouts.
BibTeX  Entry
@InProceedings{giannopoulou_et_al:LIPIcs:2017:6930,
author = {Archontia C. Giannopoulou and Michal Pilipczuk and JeanFlorent Raymond and Dimitrios M. Thilikos and Marcin Wrochna},
title = {{Cutwidth: Obstructions and Algorithmic Aspects}},
booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
pages = {15:115:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770231},
ISSN = {18688969},
year = {2017},
volume = {63},
editor = {Jiong Guo and Danny Hermelin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6930},
URN = {urn:nbn:de:0030drops69306},
doi = {10.4230/LIPIcs.IPEC.2016.15},
annote = {Keywords: cutwidth, obstructions, immersions, fixedparameter tractability}
}
09.02.2017
Keywords: 

cutwidth, obstructions, immersions, fixedparameter tractability 
Seminar: 

11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Issue date: 

2017 
Date of publication: 

09.02.2017 