On computing tree and path decompositions with metric constraints on the bags

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 : We here investigate on the complexity of computing the tree-length and the tree-breadth of any graph G, that are respectively the best possible upper-bounds on the diameter and the radius of the bags in a tree decomposition of G. Path-length and path-breadth are similarly defined and studied for path decompositions. So far, it was already known that tree-length is NP-hard to compute. We here prove it is also the case for tree-breadth, path-length and path-breadth. Furthermore, we provide a more detailed analysis on the complexity of computing the tree-breadth. In particular, we show that graphs with tree-breadth one are in some sense the hardest instances for the problem of computing the tree-breadth. We give new properties of graphs with tree-breadth one. Then we use these properties in order to recognize in polynomial-time all graphs with tree-breadth one that are planar or bipartite graphs. On the way, we relate tree-breadth with the notion of k-good tree decompositions (for k = 1), that have been introduced in former work for routing. As a byproduct of the above relation, we prove that deciding on the existence of a k-good tree decomposition is NP-complete (even if k = 1). All this answers open questions from the literature.
Type de document :
Rapport
[Research Report] RR-8842, INRIA Sophia Antipolis - Méditerranée; LRI - CNRS, University Paris-Sud. 2016, pp.66
Liste complète des métadonnées

https://hal.inria.fr/hal-01254917
Contributeur : Guillaume Ducoffe <>
Soumis le : samedi 16 janvier 2016 - 10:40:47
Dernière modification le : samedi 18 février 2017 - 01:20:41
Document(s) archivé(s) le : dimanche 17 avril 2016 - 10:10:59

Fichier

RR-8842.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01254917, version 1
  • ARXIV : 1601.01958

Citation

Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse. On computing tree and path decompositions with metric constraints on the bags. [Research Report] RR-8842, INRIA Sophia Antipolis - Méditerranée; LRI - CNRS, University Paris-Sud. 2016, pp.66. <hal-01254917>

Partager

Métriques

Consultations de
la notice

156

Téléchargements du document

79