Approximate minimum cuts and their enumeration
We show that every α-approximate minimum cut in a connected graph is the unique minimum (S,T)-terminal cut for some subsets S and T of vertices each of size at most ⌊2α⌋+1. This leads to an alternative proof that the number of α-approximate minimum cuts in a n-vertex connected graph is n^O(α) and they can all be enumerated in deterministic polynomial time for constant α.
READ FULL TEXT