Random Algorithms for the Loop Cutset Problem

Ann Becker, Reuven Bar-Yehuada, Dan Geiger

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