Abstract
Cutset conditioning is one of the methods of solving reasoning tasks for graphical models, especially when space restrictions make inference (e.g., jointree-clustering) algorithms infeasible. The wcutset is a natural extention of the method to a hybrid algoritm that performs search on the conditioning variables and inference on the remaining problems of induced width bounded by w. This paper takes a fresh look at these methods through the spectrum of AND/OR search spaces for graphical models. The resulting AND/OR cutset method is a strict improvement over the traditional one, often by exponential amounts.