Minimum size tree-decompositions

作者：Li, Bi; Moataz, Fatima Zahra; Nisse, Nicolas^*; Suchan, Karol

来源：Discrete Applied Mathematics, 2018, 245: 109-127.

DOI：10.1016/j.dam.2017.01.030

• Tree-decomposition
• Treewidth
• NP-hard

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.

• 出版日期2018-8-20
• 单位西安电子科技大学