Skip to Main content Skip to Navigation
Journal articles

On the Complexity of Computing Treebreadth

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 (or more generally, a triangle-free graph, resp., a K 3,3-minor-free graph), has treebreadth one.
Complete list of metadatas

Cited literature [39 references]  Display  Hide  Download

https://hal.inria.fr/hal-02528905
Contributor : Guillaume Ducoffe <>
Submitted on : Thursday, April 2, 2020 - 7:42:02 AM
Last modification on : Wednesday, October 14, 2020 - 4:20:55 AM

File

DLN-AlgorithmicaRevised_submit...
Files produced by the author(s)

Identifiers

Citation

Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse. On the Complexity of Computing Treebreadth. Algorithmica, Springer Verlag, inPress, ⟨10.1007/s00453-019-00657-7⟩. ⟨hal-02528905⟩

Share

Metrics

Record views

83

Files downloads

211