ICS Theory Group

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(ckn6k) 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.