Skip to Main content Skip to Navigation
Conference papers

Lean Tree-Cut Decompositions: Obstructions and Algorithms

Abstract : 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.
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download
Contributor : Dimitrios Thilikos <>
Submitted on : Friday, November 1, 2019 - 12:08:09 PM
Last modification on : Thursday, November 26, 2020 - 4:00:02 PM
Long-term archiving on: : Sunday, February 2, 2020 - 1:14:36 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




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



Record views


Files downloads