A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems

✍ Scribed by Yang Dai; Kazuo Iwano; Naoki Katoh

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 556 KB
• Volume: 64
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00175-0

✦ Synopsis

Recently Karger proposed a new randomized algorithm for finding a minimum cut of an n-vertex graph (weighted or unweighted) with probability fi (a-'). In this paper we present a new probabilistic analysis of Karger's randomized algorithm for a few classes of unweighted graphs. For random graphs whose edges are selected with a given probability p. (log n) /n 6 p < 1, we show that the expectation of success probability of the algorithm is R (p/n). We also investigate a class of graphs with special structure that consists of two n-cliques and y( n -1) edges between the two cliques. Here y is a parameter satisfying 0 < y < 1 that makes these r(n -1) edges a unique minimum cut. We show that the algorithm finds the unique minimum cut with probability n(y/nY). @ 1997 Elsevier Science B.V.