Randomized algorithms for the loop cutset problem and their application in genetic linkage analysis

Dan Geiger , Computer Science Department, Technion.

We show how to find a minimum loop cutset in an undirected graph with high probability. We discuss the application of this result to genetic linkage analysis. The algorithm outputs a minimum loop cutset after O(c6^{k} k n) 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 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 loop cutset than the ones found by the best deterministic algorithms known. This algorithm has been implemented into FASTLINK 4.1 and is used worldwide by geneticists. Examples on real and simulated data will be presented. The talk is self contained. Joint work with Ann Becker, Reuven Bar-Yehuda, and Alejandro Schaffer.