On the Practical Significance of Hypertree vs. Tree Width.

Rina Dechter, Lars Otten, and Radu Marinesu

In 2000, [4] presented a new graph parameter, the hypertree width, and showed that it provides a broader characterization of tractable constraint networks than the treewidth. In 2005, [5] extended this result to general probabilistic graphical models, showing that the hypertree width yields bounds on inference algorithms when functions are expressed relationally. The main contribution of this paper is in demonstrating empirically that in practice the bounding power of the treewidth is still superior to the hypertree width for many benchmark instances of both probabilistic and deterministic networks. Specifically, we show that the treewidth yields a far tighter bound on the algorithm's performance when the graphical model has a low level of determinism. A secondary theoretical contribution of the paper is in showing that the hypertree width bound is also relevant to search algorithms and to functions which are specified via decision trees.