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 metadata

Cited literature [39 references]  Display  Hide  Download
Contributor : Guillaume Ducoffe Connect in order to contact the contributor
Submitted on : Thursday, April 2, 2020 - 7:42:02 AM
Last modification on : Friday, July 2, 2021 - 11:20:43 AM


Files produced by the author(s)



Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse. On the Complexity of Computing Treebreadth. Algorithmica, Springer Verlag, 2020, 82 (6), pp.1574-1600. ⟨10.1007/s00453-019-00657-7⟩. ⟨hal-02528905⟩



Record views


Files downloads