Stable and Dynamic Minimum Cuts
Pages 273 - 287
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 .
References
[1]
Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, New York (1993)
[2]
de Berg, M., Sadhukhan, A., Spieksma, F.: Stable approximation algorithms for the dynamic broadcast range-assignment problem. In: 18th Scandinavian Symposium and Workshops on Algorithm Theory, pp. 15:1–15:21 (2022)
[3]
de Berg, M., Sadhukhan, A., Spieksma, F.: Stable approximation algorithms for dominating set and independent set. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023), pp. 27:1–27:19 (2023)
[4]
Bernstein, A., Dudeja, A.: Online matching with recourse: random edge arrivals. In: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020), pp. 11:1–11:16 (2020)
[5]
Feldkord, B., et al.: Fully-dynamic bin packing with little repacking. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), pp. 51:1–51:24 (2018)
[6]
Goranci, G., Henzinger, M., Nanongkai, D., Saranurak, T., Thorup, M., Wulff-Nilsen, C.: Fully dynamic exact edge connectivity in sublinear time. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 70–86. SIAM (2023)
[7]
Goranci G, Henzinger M, and Thorup M Incremental exact min-cut in polylogarithmic amortized update time ACM Trans. Algorithms (TALG) 2018 14 2 1-21
[8]
Gu, A., Gupta, A., Kumar, A.: The power of deferral: maintaining a constant-competitive steiner tree online. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pp. 525–534 (2013)
[9]
Gupta, A., Kumar, A., Stein, C.: Maintaining assignments online: matching, scheduling, and flows. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 468–479. SIAM (2014)
[10]
Han, X., Makino, K.: Online minimization knapsack problem. In: Bampis, E., Jansen, K. (eds.) Approximation and Online Algorithms. WAOA 2009. LNCS, vol. 5893, pp. 182–193. Springer, Berlin, Heidelberg (2010).
[11]
Hasheminezhad M, McKay BD, and Reeves T Recursive generation of simple planar 5-regular graphs and pentangulations J. Graph Algorithms Appl. 2011 15 3 417-436
[12]
Henzinger, M., Noe, A., Schulz, C.: Practical fully dynamic minimum cut algorithms. In: Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pp. 13–26 (2022)
[13]
Imase M and Waxman BM Dynamic steiner tree problem SIAM J. Discret. Math. 1991 4 3 369-384
[14]
Megow N, Skutella M, Verschae J, and Wiese A The power of recourse for online MST and TSP SIAM J. Comput. 2016 45 3 859-880
[15]
Thorup M Fully-dynamic min-cut Combinatorica 2007 27 1 91-127
[16]
Thorup, M., Karger, D.R.: Dynamic graph algorithms with applications. In: Scandinavian Workshop on Algorithm Theory, pp. 1–9 (2000)
[17]
Wasim, O., King, V.: Fully dynamic sequential and distributed algorithms for max-cut. In: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020), pp. 33:1–33:19 (2020)
Recommendations
Cuts leaving components of given minimum order
For a connected graph G, the restricted edge-connectivity @l"p(G) is defined as the minimum cardinality of an edge-cut over all edge-cuts S such that each component of G-S contains at least p vertices. In the present paper we introduce the more general ...
Global minimum cuts in surface embedded graphs
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithmsWe give a deterministic algorithm to find the minimum cut in a surface-embedded graph in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, our algorithm computes the minimum cut in gO(g)n log log n time, matching ...
Solving -stable instances of k-terminal cut with isolating cuts
AbstractThe k-terminal cut problem, also known as the multiterminal cut problem, is defined on an edge-weighted graph with k distinct vertices called “terminals.” The goal is to remove a minimum weight collection of edges from the graph such that there is ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Mar 2024
448 pages
ISBN:978-981-97-0565-8
DOI:10.1007/978-981-97-0566-5
- Editors:
- Ryuhei Uehara,
- Katsuhisa Yamanaka,
- Hsu-Chun Yen
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 18 March 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 02 Mar 2025