Randomized Algorithms for the Loop Cutset Problem

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(c 6^k kn) steps with probability at least 1 - (1 - 1/(6^k))^c6^k, where c > 1 is a constant 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.

References in corpus (1)

• Bounded Conditioning: Flexible Inference for Decisions under Scarce Resources

Cited by in corpus (10)

• Slightly Superexponential Parameterized Problems
• On Feedback Vertex Set: New Measure and New Structures
• Tree-Structure Expectation Propagation for LDPC Decoding over the BEC
• Tree-Structure Expectation Propagation for LDPC Decoding in Erasure Channels
• Faster deterministic Feedback Vertex Set
• Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set
• Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable
• On group feedback vertex set parameterized by the size of the cutset
• Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms
• Detecting Feedback Vertex Sets of Size $k$ in $O^{\star }(2.7^k)$ Time