Li, B., Moataz, F. Z., Nisse, N., & Suchan, K. (2018). Minimum size treedecompositions. Discret Appl. Math., 245, 109–127.
Abstract: We study in this paper the problem of computing a treedecomposition 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 treedecomposition 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 NPcomplete 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 2connected outerplanar graphs. (C) 2017 Elsevier B.V. All rights reserved.
