A key tool in many augmentation/splitting off algorithms (e.g., in [1]}, [2]}, [3]}, [4]}, [5]}) is that of extreme sets. A non-empty set of vertices \(X\subset V\)  is called an extreme set in graph \(G = (V, E)\)  if for every proper subset \(Y\subset X\) , we have \(\delta _G(Y) > \delta _G(X)\) , where \(\delta _G(X)\)  (resp., \(\delta _G(Y)\) ) is the total weight of edges with exactly one endpoint in \(X\)  (resp., \(Y\) ) in \(G\) . (If the graph is unambiguous, we drop the subscript \(G\)  and write \(\delta (\cdot )\) .) The extreme sets form a laminar family, therefore allowing an \(O(n)\) -sized representation in the form of an extreme sets tree. The main bottleneck of the Benczúr-Karger algorithm is in the construction of the extreme sets tree. They use the recursive contraction framework of Karger and Stein [6]} for this construction, which takes \(\tilde{O}(n^2)\)  time. In this paper, we obtain a faster algorithm for finding the extreme sets of a graph:
theoremExtreme
There is a randomized, Monte Carlo algorithm for finding the extreme sets tree of an undirected graph 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.
