Stable and Dynamic Minimum Cuts

Abstract

We consider the two problems of maintaining an exact minimum cut, and of maintaining a $\rho$-approximate cut, in dynamic graphs under the vertex-arrival model. We investigate the trade-off between the stability of a solution---the minimum number of vertex flips required to transform an induced bipartition into another when a new vertex arrives---and its quality. Trivially, in a graph with $n$ vertices any cut can be maintained with $n/2$ vertex flips upon a vertex arrival. For both our problems, we obtain that this trivial stability bound is tight up to constant factors, even for a clairvoyant algorithm---one that knows the entire vertex-arrival sequence in advance. When $\rho$ is large enough, we show that there are simple and stable algorithms for maintaining a $\rho$-approximate cut in both general and planar graphs. In view of the negative results, we also investigate the quality-stability trade-off in the amortized sense. For maintaining exact minimum cuts, we show that the trivial $O(n)$ amortized stability bound is also tight up to constant factors. However, for maintaining a $\rho$-approximate cut, we show a lower bound of $\Omega(\frac{n}{\rho^2})$ average vertex flips, and give a (clairvoyant) algorithm with amortized stability $O\left( \frac{n \log n}{\rho \log \rho} \right)$.