Minimum Size Tree-Decompositions

Bi Li 1, 2 Fatima Zahra Moataz 1 Nicolas Nisse 1, 3
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 : 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 program- ming algorithms based on tree-decompositions is dominated by the size (number of bags) of the tree- decompositions. It is then interesting to try 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. 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. On going work also suggests it is polynomial for k = 3.
Type de document :
Communication dans un congrès
9th International colloquium on graph theory and combinatorics (ICGT), 2014, Grenoble, France. 2014


https://hal.inria.fr/hal-01023904
Contributeur : Nicolas Nisse <>
Soumis le : mardi 15 juillet 2014 - 14:09:01
Dernière modification le : jeudi 17 juillet 2014 - 10:13:41
Document(s) archivé(s) le : vendredi 21 novembre 2014 - 18:05:59

Fichier

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

Identifiants

  • HAL Id : hal-01023904, version 1

Collections

Citation

Bi Li, Fatima Zahra Moataz, Nicolas Nisse. Minimum Size Tree-Decompositions. 9th International colloquium on graph theory and combinatorics (ICGT), 2014, Grenoble, France. 2014. <hal-01023904>

Partager

Métriques

Consultations de
la notice

181

Téléchargements du document

172