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 , 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.
Type de document :
Communication dans un congrès
Veli Mäkinen; Simon J. Puglisi; Leena Salmela. 27th International Workshop on Combinatorial Algorithms, IWOCA 2016, Aug 2016, Helsinki, Finland. Springer International Publishing, 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), pp.3-15, 2016, Combinatorial Algorithms. 〈http://iwoca2016.cs.helsinki.fi/〉. 〈10.1007/978-3-319-44543-4_1〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01354996
Contributeur : Guillaume Ducoffe <>
Soumis le : lundi 22 août 2016 - 08:50:42
Dernière modification le : jeudi 20 juillet 2017 - 09:29:00
Document(s) archivé(s) le : mercredi 23 novembre 2016 - 12:37:59

Fichier

DLN-IWOCA16.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse. On the Complexity of Computing Treebreadth. Veli Mäkinen; Simon J. Puglisi; Leena Salmela. 27th International Workshop on Combinatorial Algorithms, IWOCA 2016, Aug 2016, Helsinki, Finland. Springer International Publishing, 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), pp.3-15, 2016, Combinatorial Algorithms. 〈http://iwoca2016.cs.helsinki.fi/〉. 〈10.1007/978-3-319-44543-4_1〉. 〈hal-01354996〉

Partager

Métriques

Consultations de
la notice

247

Téléchargements du document

57