On the Complexity of Computing Treebreadth - Archive ouverte HAL Access content directly
Journal Articles Algorithmica Year : 2020

On the Complexity of Computing Treebreadth

(1, 2) , (3) , (4)
1
2
3
4

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.
Fichier principal
Vignette du fichier
DLN-AlgorithmicaRevised_submitted.pdf (594.15 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02528905 , version 1 (02-04-2020)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More