The rest of the proof will focus on bounding the cumulative running time of the recursive instances of the algorithm.
Our first step is to show that the expected number of iterations in any subproblem before we obtain an \(X\)  that satisfies eq:X is a constant:

Suppose \(s, t\)  are vertices chosen uniformly at random from \(V^{\rm gen}\) , and let \(\phi := \lambda (s, t)\)  be the \(s-t\)  connectivity in \(G^{\rm gen}\) . Then, \(X := V^{\rm gen}\setminus {\rm ct}(s, \phi )\)  satisfies eq:X with probability \(\ge 1/32\) .

To show this, we first need to establish some properties of the random transformation that changes edge weights from \(w\)  to \(w^{\prime }\) .
First, we establish uniqueness of the minimum \(s-t\)  cut for any vertex pair \(s, t\in V\)  under \(w^{\prime }\) . We need the Isolation Lemma for this purpose:
[Isolation Lemma [1]}]
Let \(m\)  and \(N\)  be positive integers and let \(\cal F\)  be a collection of subsets of \(\lbrace 1, 2, \ldots , m\rbrace \) . Suppose each element \(x\in \lbrace 1, 2, \ldots , m\rbrace \)  receives a random number \(r(x)\)  uniformly and independently from \(\lbrace 1, 2, \ldots , N\rbrace \) . Then, with probability \(\ge 1-m/N\) , there is a unique set \(S\in {\cal F}\)  that minimizes \(\sum _{x\in S} r(x)\) .

We choose \(N = m\cdot n^d\)  for some constant \(d > 0\) . (Note that this increases the edge weights from \(w\)  to \(w^{\prime }\)  by a \(\operatorname{poly}(n)\)  factor only, thereby ensuring that the efficiency of elementary operations is not affected.) Then, we can apply the Isolation Lemma to prove the following property:

Fix any vertex \(s\in V^{\rm gen}\) . For every vertex \(t\in V^{\rm gen}\setminus \lbrace s\rbrace \) , the minimum \(s-t\)  cut under edge weights \(w^{\prime }\)  is unique with probability \(\ge 1-1/n^d\) . Moreover, let \(t, t^{\prime }\in V^{\rm gen}\setminus \lbrace s\rbrace \) . With probability at least \(\ge 1 - 1/n^d\) , one of the following must hold: (a) \(\lambda (s, t)\ne  \lambda (s, t^{\prime })\) , or (b) the unique minimum \(s-t\)  cut is identical to the unique minimum \(s-t^{\prime }\)  cut in \(G^{\rm gen}\) .


We first establish the uniqueness of the minimum \(s-t\)  cut. Note that by lem:consistency, the only candidates for minimum \(s-t\)  cut under \(w^{\prime }\)  are the minimum \(s-t\)  cuts under \(w\) . For any two such cuts \(X, Y\subset V^{\rm gen}\) , we have \(\delta _w(X) = \delta _w(Y)\) , i.e., \(mN\cdot \delta _w(X) = mN\cdot \delta _w(Y)\) . Therefore, the \(s-t\)  minimum cuts under \(w^{\prime }\)  are those minimum \(s-t\)  cuts \(X\)  under \(w\)  that have the minimum value of \(r(X)\) , which is defined as the sum of \(r(u, v)\)  over all edges \((u, v)\)  with exactly one endpoint in \(X\) . The uniqueness of the minimum \(s-t\)  cut under edge weights \(w^{\prime }\)  now follows from lem:isolation by setting \(\cal F\)  to the collection of subsets of edges that form the minimum \(s-t\)  cuts under edge weights \(w\) .
