Benczúr and Karger's algorithm repeatedly constructs augmentation chains until there are no extreme sets with demand at least 2 in the current graph. By applying lem:partial-solution after each iteration, any optimal solution to the instance after that iteration can be augmented to an optimal solution to the instance before that iteration. At the end, only extreme sets with demand 1 remain in the instance, at which point Benczúr and Karger use an algorithm of Naor et al. [1]} that runs in \(O(n)\)  time given the min-cut cactus representation of \(G\) . Using the \(\tilde{O}(m)\) -time min-cut cactus algorithm of Karger and Panigrahi [2]}, this last step takes \(\tilde{O}(m)\)  time.
