ALCOMFT-TR-03-123

Frank van den Eijkhof, Hans L. Bodlaender and Arie M.C.A. Koster
Safe reduction rules for weighted treewidth
Utrecht. Work packages 2 and 5. December 2003.

Abstract: Several sets of reductions rules are known for preprocessing a graph when computing its treewidth. In this paper, we give reduction rules for a weighted variant of treewidth, motivated by the analysis of algorithms for probabilistic networks. We present two general reduction rules that are safe for weighted treewidth. They generalise many of the existing reduction rules for treewidth. Experimental results show that these reduction rules can significantly reduce the problem size for several instances of real-life probabilistic networks.

Postscript file: ALCOMFT-TR-03-123.ps.gz (143 kb).