TY - GEN
T1 - Lean tree-cut decompositions
T2 - 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019
AU - Giannopoulou, Archontia C.
AU - Kwon, O. Joung
AU - Raymond, Jean Florent
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos.
PY - 2019/3/1
Y1 - 2019/3/1
N2 - 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.
AB - 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.
KW - Immersions
KW - Lean decompositions
KW - Obstructions
KW - Parameterized algorithms
KW - Tree-cut width
UR - http://www.scopus.com/inward/record.url?scp=85074917232&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85074917232&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2019.32
DO - 10.4230/LIPIcs.STACS.2019.32
M3 - Conference contribution
AN - SCOPUS:85074917232
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019
A2 - Niedermeier, Rolf
A2 - Paul, Christophe
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 13 March 2019 through 16 March 2019
ER -