Stable and Dynamic Minimum Cuts

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

We consider the problems of maintaining exact minimum cuts and -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 is relaxed more than certain thresholds, we show that there are simple and stable algorithms for maintaining a -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 -approximate cut, we show a lower bound of average vertex flips, and give a (clairvoyant) algorithm with amortized stability .

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Proceedings
EditorsRyuhei Uehara, Katsuhisa Yamanaka, Hsu-Chun Yen
PublisherSpringer
Pages273-287
Number of pages15
ISBN (Print)9789819705658
DOIs
Publication statusPublished - 2024
Event18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024 - Kanazawa, Japan
Duration: 18 Mar 202420 Mar 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14549 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024
Country/TerritoryJapan
CityKanazawa
Period18/03/2420/03/24

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.

Keywords

  • Approximation
  • Dynamic Minimum Cut
  • Stability

Fingerprint

Dive into the research topics of 'Stable and Dynamic Minimum Cuts'. Together they form a unique fingerprint.

Cite this