Randomized Algorithms for the Loop Cutset Problem

R. Bar-Yehuda, A. Becker, D. Geiger

We show how to find a minimum weight loop cutset in a Bayesian network with high probability. Finding such a loop cutset is the first step in the method of conditioning for inferen…