Lean Tree-Cut Decompositions: Obstructions and Algorithms - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2019

Lean Tree-Cut Decompositions: Obstructions and Algorithms


The notion of tree-cut width has been introduced by Wollan in [The structure of graphs not admitting a fixed immersion, Journal of Combinatorial Theory, Series B, 110:47-66, 2015]. It is defined via tree-cut decompositions, which are tree-like decompositions that highlight small (edge) cuts in a graph. In that sense, tree-cut decompositions can be seen as an edge-version of tree-decompositions and have algorithmic applications on problems that remain intractable on graphs of bounded treewidth. In this paper, we prove that every graph admits an optimal tree-cut decomposition that satisfies a certain Menger-like condition similar to that of the lean tree decompositions of Thomas [A Menger-like property of tree-width: The finite case, Journal of Combinatorial Theory, Series B, 48(1):67-76, 1990]. This allows us to give, for every k ∈ N, an upper-bound on the number immersion-minimal graphs of tree-cut width k. Our results imply the constructive existence of a linear FPT-algorithm for tree-cut width.
Fichier principal
Vignette du fichier
LIPIcs-STACS-2019-32.pdf (649.91 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-02342775 , version 1 (01-11-2019)





Archontia C. Giannopoulou, O-Joung Kwon, Jean-Florent Raymond, Dimitrios M. Thilikos. Lean Tree-Cut Decompositions: Obstructions and Algorithms. STACS 2019 - 36th International Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.32:1--32:14, ⟨10.4230/LIPIcs.STACS.2019.32⟩. ⟨lirmm-02342775⟩
72 View
72 Download



Gmail Facebook X LinkedIn More