{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T14:51:41Z","timestamp":1774191101856,"version":"3.50.1"},"reference-count":0,"publisher":"Journal of Graph Algorithms and Applications","issue":"1","license":[{"start":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T00:00:00Z","timestamp":1773964800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JGAA"],"abstract":"<jats:p>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)$.\u00a0<\/jats:p>","DOI":"10.7155\/jgaa.v30i1.2998","type":"journal-article","created":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T13:55:04Z","timestamp":1774101304000},"page":"89-107","source":"Crossref","is-referenced-by-count":0,"title":["Stable and Dynamic Minimum Cuts"],"prefix":"10.7155","volume":"30","author":[{"given":"Andres","family":"Lopez Martinez","sequence":"first","affiliation":[]},{"given":"Mark","family":"De Berg","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2547-3782","authenticated-orcid":false,"given":"Frits","family":"Spieksma","sequence":"additional","affiliation":[]}],"member":"4175","published-online":{"date-parts":[[2026,3,20]]},"container-title":["Journal of Graph Algorithms and Applications"],"original-title":[],"link":[{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/2998\/3023","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/2998\/3023","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T13:55:11Z","timestamp":1774187711000},"score":1,"resource":{"primary":{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/view\/2998"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,20]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,1,17]]}},"URL":"https:\/\/doi.org\/10.7155\/jgaa.v30i1.2998","relation":{},"ISSN":["1526-1719"],"issn-type":[{"value":"1526-1719","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,20]]}}}