Stable and Dynamic Minimum Cuts

Read full text Summarise with VIRAT
Authors: Andrés López Martínez, Mark de Berg, Frits C. R. Spieksma
Cited by: 0
References: 17

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

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)$.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Advanced Graph Theory Research Optimization and Search Problems

Publication details

Journal / source
Journal of Graph Algorithms and Applications
Volume
30
Issue
1
Pages
89–107
Publication date
20 March 2026
Language
EN