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 metadatas

Cited literature [32 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02342775
Contributor : Dimitrios Thilikos <>
Submitted on : Friday, November 1, 2019 - 12:08:09 PM
Last modification on : Monday, June 8, 2020 - 11:14:02 AM
Document(s) archivé(s) le : Sunday, February 2, 2020 - 1:14:36 PM

File

LIPIcs-STACS-2019-32.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

Archontia 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⟩

Share

Metrics

Record views

40

Files downloads

23