Abstract
Bayesian networks allow for the compactrepresentation of uncertain knowledge. There is strong evidence from computational complexity that performing inference in them takes timeexponential in the network treewidth, which measures the complexity of the model.Bounding the treewidth of the networks decreases their representational power. We can counter that decrease without increasing the co…