Tree decompositions with small cost Original Research Article

The f-cost of a tree decomposition image for a function image is defined as image. This measure associates with the running time or memory use of some algorithms that use the tree decomposition. In this paper, we investigate the problem to find tree decompositions of minimum f-cost. A function image is fast, if for every image: image. We show that for fast functions f, every graph G has a tree decomposition of minimum f-cost that corresponds to a minimal triangulation of G; if f is not fast, this does not hold. We give polynomial time algorithms for the problem, assuming f is a fast function, for graphs that have a polynomial number of minimal separators, for graphs of treewidth at most two, and for cographs, and show that the problem is NP-hard for bipartite graphs and for cobipartite graphs. We also discuss results for a weighted variant of the problem derived of an application from probabilistic networks.