Exact Algorithms for Loop Cutset

Abstract

The LOOP CUTSET problem was historically posed by Pearl as a subroutine in Pearl’s algorithm for computing inference in probabilistic networks. The efficiency of the algorithm that solves the probabilistic inference highly depends on the size of the smallest known LOOP CUTSET. This justifies the search for exact algorithms for find- ing a minimum LOOP CUTSET. In this thesis we are investigating the algorithmic complexity of the problem. We will look at both the unparameterized problem and the problem parameterized by the treewidth of the input graph. For both we give an exact exponential time algorithm. The running times of these algorithms are O(1.7548n ) and O(4tw ) respectively, where tw is the treewidth of the input graph. Finally, we prove a lower bound of 3tw for the parameterized problem.