Stable and Dynamic Minimum Cuts

We consider the problems of maintaining exact minimum cuts and \(\rho \) -approximate cuts 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 the two problems, in general graphs as well as in planar graphs, 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 relaxed more than certain thresholds, 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 \(\varOmega (\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) \) .