Our main observation is that if an extreme set \(Y\)  partially overlaps the complement \(X\)  of a Cut Threshold, then it must actually be wholly contained in \(X\) . (Intuitively, one may interpret this property as saying that an extreme set and a Cut Threshold are non-crossing, although our property is actually stronger, and only the non-crossing property does not suffice for our algorithm.) This allows us to design a divide and conquer algorithm that runs a recursion on two subproblems generated by contracting each side of a carefully chosen Cut Threshold. The above property ensures that every extreme set in the original problem continues to be an extreme set in either of the two subproblems. In order to bound the depth of recursion, it is important to use a Cut Threshold that produces a balanced partition of vertices. We ensure this by adapting a recent observation of Abboud et al. [1]} which asserts that a Cut Threshold based on the connectivity between two randomly chosen vertices is balanced with constant probability. One additional complication is that while the contraction of the Cut Threshold (or its complement) does not eliminate any extreme set, it might actually add new extreme sets. We run a post-processing phase where we use a dynamic tree data structure to eliminate these spurious extreme sets added by the recursive algorithm.
