Computing All Small Cuts in an Undirected Network

Abstract

Let $\lambda({\cal N})$ denote the weight of a minimum cut in an edge-weighted undirected network ${\cal N}$, and n and m denote the numbers of vertices and edges, respectively. It is known that $O(n^{2k})$ is an upper bound on the number of cuts with weights less than $k\lambda({\cal N})$, where $k\geq 1$ is a given constant. This paper first shows that all cuts of weights less than $k\lambda({\cal N})$ can be enumerated in $O(m^2n+n^{2k}m)$ time without using the maximum flow algorithm. The paper then proves for $k < \four$ that $n\choose 2$ is a tight upper bound on the number of cuts of weights less than $k\lambda({\cal N})$, and that all those cuts can be enumerated in $O(m^2n+mn^2\log n)$ time.