I'm stuck with one of my homework exercises:Consider the following variant of Kargers algorithm for finding a minimum s-t cut, i.e., a minimum cut separating two specific given nodes s and t: As in the original algorithm, edges are iteratively contracted. In any iteration, let s and t denote the possibly contracted nodes that contain the original nodes s and t, respectively. To ensure that s and t do not get contracted, at each iteration any edges connecting s and t are deleted, and a random edge to contract is selected from the remaining edges.Give an example showing that the probability that this method finds a minimum s-t cut can be exponentially small.I know how Karger's algorithm works, but I'm not sure why the probability is exponentially small and how can I show that by giving an example.Any hint would be helpful.
Showing that Karger's contraction algorithm has exponentially small probability of finding an optimum
algorithms;graph theory;algorithm analysis;graphs;randomized algorithms