The Taub Faculty of Computer Science Events and Talks

Many intractable problems on graphs, can be efficiently solved for trees or forests. Tree decompositions allow taking advantage of this fact to handle general graphs by grouping nodes into bags and extracting a tree structure. The problem at hand is then solved independently for the subgraphs induced by the bags, and then the results can be efficiently combined. Tree decompositions have a plethora of applications, including join optimization in databases, constraint-satisfaction problems, and inference in probabilistic graphical models. Unfortunately, finding a good tree decomposition is not an easy task. We explore the approach of generating many (or all) tree decompostions, and choosing the best. Our proposed enumeration algorithm runs in incremental polynomial time (the delay after the Nth answer is polynomial in N+n, where n is the size of the input). It also enumerates the minimal triangulations of a graph, and can incorporate any method for (ordinary, single result) triangulation or tree decomposition, serving as an anytime algorithm to improve such a method. I will describe the algorithm along with an experimental study of an implementation on real graphs of two kinds: database queries and Bayesian networks. Our experiments show that the algorithm improves upon central quality measures over the underlying tree decompositions, and is able to produce a large number of high-quality decompositions. The presentation will be given in English, no prior knowledge is assumed.