Cutwidth: obstructions and algorithmic aspects

DOI10.4230/LIPICS.IPEC.2016.15MaRDI QIDQ4634398zbMATH OpenFDO

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

Publication date 10 April 2018

Full work available at URL https://arxiv.org/abs/1606.05975

zbMATH Keywords

cutwidthfixed-parameter tractabilityimmersionsobstructions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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}logk)}$. 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}logk)}cdotn$, where $k$ is the optimum width and $n$ is the number of vertices. While being slower by a $logk$-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.

Recommendations

• Cutwidth: obstructions and algorithmic aspects
• Cutwidth I: A linear time fixed parameter algorithm
• Derivation of algorithms for cutwidth and related graph layout parameters
• Algorithmic applications of tree-cut width
• Algorithmic applications of tree-cut width

Cited in

(11)

• Derivation of algorithms for cutwidth and related graph layout parameters
• Cutwidth: obstructions and algorithmic aspects
• Sparse obstructions for minor-covering parameters
• Computing the chromatic number using graph decompositions via matrix rank
• Towards Algorithmic Cut-Introduction
• Algorithmic applications of tree-cut width
• Lower bounds for dynamic programming on planar graphs of bounded cutwidth
• Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
• Algorithmic applications of tree-cut width
• Mathematical Foundations of Computer Science 2003
• Cutwidth I: A linear time fixed parameter algorithm

This page was built for publication: Cutwidth: obstructions and algorithmic aspects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4634398)