Minimum Size Tree-decompositions

Abstract : Tree-decompositions are the cornerstone 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 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 extended abstract, we consider the problem of computing a tree-decomposition of a graph with width at most k and minimum size. 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 :
Communication dans un congrès
LAGOS 2015 – VIII Latin-American Algorithms, Graphs and Optimization Symposium, May 2015, Beberibe, Ceará, Brazil
Liste complète des métadonnées


https://hal.inria.fr/hal-01162695
Contributeur : Fatima Zahra Moataz <>
Soumis le : jeudi 11 juin 2015 - 11:08:07
Dernière modification le : mercredi 14 décembre 2016 - 01:07:20
Document(s) archivé(s) le : mardi 25 avril 2017 - 06:39:09

Fichier

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

Identifiants

  • HAL Id : hal-01162695, version 1

Collections

Citation

Bi Li, Fatima Zahra Moataz, Nicolas Nisse, Karol Suchan. Minimum Size Tree-decompositions. LAGOS 2015 – VIII Latin-American Algorithms, Graphs and Optimization Symposium, May 2015, Beberibe, Ceará, Brazil. <hal-01162695>

Partager

Métriques

Consultations de
la notice

181

Téléchargements du document

89