Size-Constrained Tree Decompositions

Abstract : Tree-Decompositions are the corner-stone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute tree-decompositions with small width. However, practical algorithms computing tree-decompositions only exist for graphs with treewidth less than 4. In such graphs, the time-complexity of dynamic programming algorithms based on tree-decompositions is dominated by the size (number of bags) of the tree-decompositions. It is then interesting to minimize the size of the tree-decompositions. In this report, we consider the problem of computing a tree-decomposition of a graph with width at most k and minimum size. More precisely, we focus on the following problem: given a fixed k ≥ 1, what is the complexity of computing a tree-decomposition of width at most k with minimum size in the class of graphs with treewidth at most k? We prove that the problem is NP-complete for any fixed k ≥ 4 and polynomial for k ≤ 2; for k = 3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs.
Type de document :
Rapport
[Research Report] INRIA Sophia-Antipolis. 2014
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01074177
Contributeur : Fatima Zahra Moataz <>
Soumis le : lundi 13 octobre 2014 - 11:27:02
Dernière modification le : samedi 17 septembre 2016 - 01:36:46
Document(s) archivé(s) le : jeudi 15 janvier 2015 - 14:55:31

Fichier

ReportV1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01074177, version 1

Collections

Citation

Bi Li, Fatima Zahra Moataz, Nicolas Nisse, Karol Suchan. Size-Constrained Tree Decompositions. [Research Report] INRIA Sophia-Antipolis. 2014. 〈hal-01074177〉

Partager

Métriques

Consultations de
la notice

243

Téléchargements du document

147