Minimum Size Tree-Decompositions

Abstract : We study in this paper the problem of computing a tree-decomposition of a graph with width at most k and minimum number of bags. 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 number of bags 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 :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2017, 〈10.1016/j.dam.2017.01.030〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01620389
Contributeur : Nicolas Nisse <>
Soumis le : jeudi 23 novembre 2017 - 15:26:18
Dernière modification le : jeudi 4 octobre 2018 - 22:12:02

Fichier

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

Identifiants

Citation

Bi Li, Fatima Zahra Moataz, Nicolas Nisse, Karol Suchan. Minimum Size Tree-Decompositions. Discrete Applied Mathematics, Elsevier, 2017, 〈10.1016/j.dam.2017.01.030〉. 〈hal-01620389〉

Partager

Métriques

Consultations de la notice

209

Téléchargements de fichiers

39