In the edge connectivity augmentation problem, we are given an undirected graph \(G = (V, E)\)  with (integer) edge weights \(w\) , and a target connectivity \(\tau > 0\) . The goal is to find a minimum weight set \(F\)  of edges on \(V\)  such that adding these edges to \(G\)  makes the graph \(\tau \) -connected. (In other words, the value of the minimum cut of the graph after the augmentation should be at least \(\tau \) .) The edge connectivity augmentation problem is known to be tractable in \(\operatorname{poly}(m, n)\)  time, where \(m\)  and \(n\)  denote the number of edges and vertices respectively in \(G\) . This was first shown by Watanabe and Nakamura [1]} for unweighted graphs, and the first strongly polynomial algorithm was obtained by Frank [2]}. Since then, several algorithms [3]}, [4]}, [5]}, [6]}, [7]} have progressively improved the running time to the current best \(\tilde{O}(n^2)\)  obtained by Benczúr and Karger [8]}.\(\tilde{O}(\cdot )\)  ignores (poly)-logarithmic factors in the running time.
In this paper, we give an algorithm to solve the edge connectivity augmentation problem using \(\operatorname{polylog}(n)\)  calls to any max-flow algorithm:

There is a randomized, Monte Carlo algorithm for the edge connectivity augmentation problem that runs in \(\tilde{O}(m) + \operatorname{polylog}(n)\cdot F(m, n)\)  time where \(F(m, n)\)  is the running time of any maximum flow algorithm on an undirected graph containing \(m\)  edges and \(n\)  vertices.

Using the current best max-flow algorithm on undirected graphs [9]},We note that for sparse graphs, there is a slightly faster max-flow algorithm that runs in \(O(m^{3/2-\delta })\)  time [10]}, where \(\delta > 0\)  is a small constant. If we use this max-flow algorithm in thm:augment, we also get a running time of \(O(m^{3/2-\delta })\)  for the augmentation problem. this yields a running time of \(\tilde{O}(m + n^{3/2})\) , thereby improving on the previous best bound of \(\tilde{O}(n^2)\) .
