Random Algorithms for the Loop Cutset Problem

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. Our random algorithm for nding a loop cutset, called RepeatedWGuessI, outputs a minimum loop cutset, afterO(c 6kkn) steps, with probability at least 1,(1, 1 6k) c6k, where c >1 is a constant specified by the user,k is the size of a minimum weight loop cutset, andnis the number of vertices. We also show empirically that a variant of this algorithm, called WRA, often finds a loop cutset that is closer to the minimum loop cutset than the ones found by the best deterministic algorithms known