On the Complexity of Computing Treebreadth

Guillaume Ducoffe 1 Sylvain Legay 2 Nicolas Nisse 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : During the last decade, metric properties of the bags of tree-decompositions of graphs have been studied. Roughly, the length and the breadth of a tree-decomposition are the maximum diameter and radius of its bags respectively. The treelength and the treebreadth of a graph are the minimum length and breadth of its tree-decompositions respectively. Pathlength and pathbreadth are defined similarly for path-decompositions. In this paper, we answer open questions of [Dragan and Köhler , Algorithmica 2014] and [Dragan, Köhler and Leitert, SWAT 2014] about the computational complexity of treebreadth, pathbreadth and pathlength. Namely, we prove that computing these graph invariants is NP-hard. We further investigate graphs with treebreadth one, i.e., graphs that admit a tree-decomposition where each bag has a dominating vertex. We show that it is NP-complete to decide whether a graph belongs to this class. We then prove some structural properties of such graphs which allows us to design polynomial-time algorithms to decide whether a bipartite graph, resp., a planar graph, has treebreadth one.
Liste complète des métadonnées

Cited literature [21 references]  Display  Hide  Download

Contributor : Guillaume Ducoffe <>
Submitted on : Monday, August 22, 2016 - 8:50:42 AM
Last modification on : Thursday, February 7, 2019 - 4:16:58 PM
Document(s) archivé(s) le : Wednesday, November 23, 2016 - 12:37:59 PM


Files produced by the author(s)



Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse. On the Complexity of Computing Treebreadth. 27th International Workshop on Combinatorial Algorithms, IWOCA 2016, Aug 2016, Helsinki, Finland. pp.3-15, ⟨10.1007/978-3-319-44543-4_1⟩. ⟨hal-01354996⟩



Record views


Files downloads