Our extreme sets algorithm is based on the isolating cuts framework that we introduced in a recent paper [1]}. (This was independently discovered by Abboud et al. [2]}.) Given a set of \(k\)  terminal vertices, this framework uses \(O(\log k)\)  max-flows to find the minimum cuts that separate each individual terminal from the remaining terminals (called isolating cuts). In the current paper, instead of using the framework directly, we use a gadget called a Cut Threshold that is defined as follows: for a given vertex \(s\)  and threshold \(\phi \ge 0\) , the Cut Threshold \({\rm ct}(s, \phi )\)  is the set of vertices \(t\)  such that the value of the minimum \(s-t\)  cut \(\lambda (s, t) \le \phi \) . We showed recently [3]} that the isolating cuts framework can be used to find the Cut Threshold for any vertex \(s\)  and threshold \(\phi \)  in \(\operatorname{polylog}(n)\)  max-flows. We use this result here, and focus on obtaining extreme sets using a Cut Threshold subroutine.
