# ICS 269, Spring 2002: Theory Seminar

## 6 December 2002:

Title: Randomized algorithms for the loop cutset problem

Ann Becker, Reuven Bar-Yehuda, and Dan Geiger

Journal of Artificial Intelligence Research, 12:219-234, 2000.

Speaker: Matthew Ba Nguyen

Abstract:
A loop cutset is a set of vertices V such that removing that set V and all
adjacent edges to V from a graph G, the resulting graph is a forest of
trees. The authors give a randomized algorithm for finding a minimum loop
cutset after O(*ckn*6^{k}) steps with probability
1 - (1 - 6^{-k})^{c6k},
where *c* > 1 is a constant specified by the user,
*k* is the minimum size of a
minimum loop cutset, and *n* is the number of vertices.