# Randomized Algorithms For The Loop Cutset Problem

## Ann Becker

Reuven Bar- Yehuda Dan Geiger Computer Science Department Technion, Haifa, 3200, Israel AN YU TA @CS TE CHNI ON A C IL
RE U V EN Q C S  T E C H N I O N  A C  I L
DANG @CS TECHNION A C IL

## Abstract

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 inference.  Our randomized algorithm for finding a loop cutset outputs a minimum loop cutset after O(cO*kn) steps with probability at least 1 - (1 - ~ ) c 6 k , where c l is a const ant specified by the user, k is the minimal size of a minimum weight loop cutset, and n is the number of vertices. We also show empirically that a variant of this algorithm often finds a loop cutset that is closer to the minimum weight loop cutset than the ones found by the best deterministic algorithms known.

## 1. Introduction

The method of conditioning is a well known inference method for the computation of pos terior probabilities in general Bayesian networks  Pearl Suermondt Cooper Peot Shachter as well as for finding MAP values and solving constraint sat isfaction problems  Dechter This method has two conceptual phases  First to find an optimal or close to optimal loop cutset and then to perform a likelihood computation for each instance of the variables in the loop cutset This method is routinely used by geneticists via several genetic linkage programs  Ott Lang Becker Geiger Schaffer A variant of this method was developed by Lange and Elston Finding a minimum weight loop cutset is NP complete and thus heuristic methods have often been applied to find a reasonable loop cutset  Suermondt Cooper Most methods in the past had no guarantee of performance and performed very badly when presented with an appropriate example   Becker and Geiger offered an algorithm that finds a loop cutset for which the logarithm of the state space is guaranteed to be at most a constant factor off the optimal value An adaptation of these approximation algonthms hh of FASTLINK  a popular software for analyzing large pedigrees with small number of genetic markers  Becker et al Similar algorithms in the context of undirected graphs are described by Bafna  Berman  and Fujito and Fujito While approximation algorithms for the loop cutset problem are quite useful it is still worthwhile to invest in finding a minimum loop cutset rather than an approximation be cause the cost of finding such a loop cutset is amortized over the many iterations of the conditioning method  In fact  one may invest an effort of complexity exponential in the size of the loop cutset in finding a minimum weight loop cutset because the second phase of the conditioning algorithm  which is repeated for many iterations  uses a procedure of such