Lesson 11

Randomized algorithm for Minimum Cut

In the minimum cut problem, one is given an undirected graph \(G(V,E)\) and is asked to find a nonempty proper set \(S \subsetneq V\) (that is, to partition the set of nodes \(V\) into two parts, \(S\) and \(V \setminus S\)) to minimize the number of edges between \(S\) and \(V \setminus S\). The following simple randomized algorithm is a basic version of Karger's algorithm.

Repeat the following operation \(n-2\) times (as usual, \(n\) is the number of nodes): choose a random edge in the graph and contract its endpoints into a single vertex (this may create multi-edges, but we remove all self-loops); at the end, two vertices remain; return the cut induced by this partition (and its value, i.e. the number of parallel edges between them).

An example of contracting an edge is presented below.

def Rand_Min_Cut(G):
    while G has more than 2 vertices:
        choose a uniformly random edge (u, v)
        delete all edges between u and v
        contract u and v into a single vertex

    return the number of edges between the two remaining vertices

Below, we prove that a fixed minimum cut survives with probability at least \(\frac{2}{n(n-1)}\). The cut survives if none of its edges is contracted during the \(n-2\) iterations. From this claim it immediately follows that by repeating the algorithm \(O(n^{2})\) times, one can reduce the error probability to any prescribed constant.

Let us estimate the required probability. Lemma. The algorithm \(\mathrm{Rand\mbox{-}Min\mbox{-}Cut}\) outputs each minimum cut of a graph with probability at least \(\frac{2}{n(n-1)}\). The running time of the algorithm is \(O(n^{2})\). Proof. Fix an arbitrary minimum cut \(C\) and denote its size by \(k\). Then \(G\) contains at least \(kn/2\) edges, since the degree of each vertex is at least \(k\). Denote by \(A_{i}\) the event that no edge from \(C\) is chosen at step \(i\). Then \[\Pr[\text{the algorithm outputs }C] = \Pr[A_{1} \cap A_{2} \cap … \cap A_{n-2}].\]

We have \[\Pr[A_{1}] \ge 1 - \frac{|C|}{|E|}\ge 1 - \frac{k}{kn/2}= 1 - \frac{2}{n}.\] After the first step, there remain \(n-1\) vertices and at least \(k(n-1)/2\) edges. Hence, \[\Pr[A_{2} \mid A_{1}] \ge 1 - \frac{2}{n-1}.\]

At step \(i\), the graph has \(n-(i-1)\) vertices. Since the size of a minimum cut is at least \(k\), the graph contains at least \(k(n-i+1)/2\) edges. Therefore, \[\Pr\!\left[ A_{i} \;\middle|\; \bigcap_{j=1}^{i-1}A_{j} \right] \ge 1 - \frac{2}{n-i+1}.\] Consequently, \[\begin{align*}\Pr\!\left[ \bigcap_{j=1}^{n-2}A_{j} \right]&= \Pr[A_{1}] \cdot \Pr[A_{2} \mid A_{1}] \cdots \Pr\!\left[ A_{n-2}\;\middle|\; \bigcap_{j=1}^{n-3}A_{j} \right] \ge \\&\ge \prod_{i=1}^{n-2}\left( 1 - \frac{2}{n-i+1}\right) = \frac{2}{n(n-1)}.\end{align*}\]◼

Thus, in order to obtain a constant error probability, it is sufficient to execute this algorithm \(O(n^{2})\) times, which results in a total running time of \(O(n^{4})\). In the exercises below, you will attempt to improve the algorithm described above by reducing its complexity to \(O(n^{2} \log^{2} n)\).