Reference: Suermondt, H. J. & Cooper, G. F. Probabilistic Inference in Multiply Connected Brief Networks Using Loop Cutsets. 1989.
Abstract: The method of conditioning permits probabilistic inference in multiply connected belief networks using an algorithm by Pearl. This method uses a select set of nodes, the loop cutset, to render the multiply connected network singly connected. We discuss the function of the nodes of the loop cutset and a condition that must be met by the nodes of the loop cutset. We show that the problem of finding a loop cutset that optimizes probabilistic inference using the method of conditioning is NP-hard. We present a heuristic algorithm for finding a small loop cutset in polynomial times, and we analyze the performance of this heuristic algorithm empirically.