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

https://hal.inria.fr/hal-01354996
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

File

DLN-IWOCA16.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

772

Files downloads

92