Approximate minimum cuts and their enumeration

11/30/2022
by   Calvin Beideman, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset