@inproceedings{21720, abstract = {We present an exact fully-dynamic minimum cut algorithm that runs in 𝑛𝑜⁡(1) deterministic update time when the minimum cut size is at most 2Θ⁡(log3/4−𝑐⁡𝑛) for any 𝑐 >0, improving on the previous algorithm of Jin, Sun, and Thorup (SODA 2024) whose minimum cut size limit is (log⁡𝑛)𝑜⁡(1). Combined with graph sparsification, we obtain the first (1 +𝜖)-approximate fully-dynamic minimum cut algorithm on weighted graphs, for any 𝜖 ≥2−Θ⁡(log3/4−𝑐⁡𝑛), in 𝑛𝑜⁡(1) randomized update time. Our main technical contribution is a deterministic local minimum cut algorithm, which replaces the randomized LocalKCut procedure from El-Hayek, Henzinger, and Li (SODA 2025).}, author = {El-Hayek, Antoine and Henzinger, Monika H and Li, Jason}, booktitle = {Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms}, issn = {1557-9468}, location = {Vancouver, Canada}, pages = {613--663}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time}}, doi = {10.1137/1.9781611978971.25}, volume = {2026}, year = {2026}, } @inproceedings{19858, abstract = {Given a graph G that undergoes a sequence of edge insertions and deletions, we study the Maximum k-Edge Coloring problem (MkEC): Having access to k different colors, color as many edges of G as possible such that no two adjacent edges share the same color. While this problem is different from simply maintaining a b-matching with b = k, the two problems are related. However, maximum b-matching can be solved efficiently in the static setting, whereas MkEC is NP-hard and even APX-hard for k ≥ 2. We present new results on both problems: For b-matching, we show a new integrality gap result and we adapt Wajc’s matching sparsification scheme [David Wajc, 2020] for the case where b is a constant. Using these as basis, we give three new algorithms for the dynamic MkEC problem: Our MatchO algorithm builds on the dynamic (2+ε)-approximation algorithm of Bhattacharya, Gupta, and Mohan [Sayan Bhattacharya et al., 2017] for b-matching and achieves a (2+ε)(k+1)/k-approximation in O(poly(log n, ε^-1)) update time against an oblivious adversary. Our MatchA algorithm builds on the dynamic (7+ε)-approximation algorithm by Bhattacharya, Henzinger, and Italiano [Sayan Bhattacharya et al., 2015] for fractional b-matching and achieves a (7+ε)(3k+3)/(3k-1)-approximation in O(poly(log n, ε^-1)) update time against an adaptive adversary. Moreover, our reductions use the dynamic b-matching algorithm as a black box, so any future improvement in the approximation ratio for dynamic b-matching will automatically translate into a better approximation ratio for our algorithms. Finally, we present a greedy algorithm with O(Δ+k) update time, which guarantees a 2.16 approximation factor.}, author = {El-Hayek, Antoine and Hanauer, Kathrin and Henzinger, Monika H}, booktitle = {4th Symposium on Algorithmic Foundations of Dynamic Networks}, isbn = {9783959773683}, issn = {1868-8969}, location = {Liverpool, United Kingdom}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{On b-matching and fully-dynamic maximum k-edge coloring}}, doi = {10.4230/LIPIcs.SAND.2025.4}, volume = {330}, year = {2025}, } @inproceedings{19982, abstract = {Dynamically maintaining the minimum cut in a graph G under edge insertions and deletion is a fundamental problem in dynamic graph algorithms for which no conditional lower bound on the time per operation exists. In an n-node graph the best known (1 + o (1))-approximate algorithm takes update time [14]. If the minimum cut is guaranteed to be (log n )o (1), a deterministic exact algorithm with n o (1) update time exists [8]. We present the first fully dynamic algorithm for (1 + o (1))-approximate minimum cut with n o(1) update time. Our main technical contribution is to show that it suffices to consider small-volume cuts in suitably contracted graphs.}, author = {El-Hayek, Antoine and Henzinger, Monika H and Li, Jason}, booktitle = {Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {New Orleans, LA, United States}, pages = {750--784}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Fully dynamic approximate minimum cut in subpolynomial time per operation}}, doi = {10.1137/1.9781611978322.22}, year = {2025}, } @inproceedings{20051, abstract = {We revisit the majority problem in the population protocol communication model, as first studied by Angluin et al. (Distributed Computing 2008). We consider a more general version of this problem known as plurality consensus, which has already been studied intensively in the literature. In this problem, each node in a system of n nodes, has initially one of k different opinions, and they need to agree on the (relative) majority opinion. In particular, we consider the important and intensively studied model of Undecided State Dynamics. Our main contribution is an almost tight lower bound on the stabilization time: we prove that there exists an initial configuration, even with bias \Delta = \omega(\sqrt{n\log n}), where stabilization requires \Omega(kn\log \frac {\sqrt n} {k \log n}) interactions, or equivalently, \Omega(k\log \frac {\sqrt n} {k \log n}) parallel time for any k = o\left(\frac {\sqrt n}{\log n}\right). This bound is tight for any k \le n^{\frac 1 2 - \epsilon}, where \epsilon >0 can be any small constant, as Amir et al.~(PODC'23) gave a O(k\log n) parallel time upper bound for k = O\left(\frac {\sqrt n} {\log ^2 n}\right).}, author = {El-Hayek, Antoine and Elsässer, Robert and Schmid, Stefan}, booktitle = {Proceedings of the ACM Symposium on Principles of Distributed Computing}, isbn = { 9798400718854}, location = {Huatulco, Mexico}, publisher = {Association for Computing Machinery}, title = {{An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model}}, doi = {10.1145/3732772.3733505}, year = {2025}, } @inproceedings{20052, abstract = {This paper revisits a fundamental distributed computing problem in the population protocol model. Provided n agents each starting with an input color in [k], the relative majority problem asks to find the predominant color. In the population protocol model, at each time step, a scheduler selects two agents that first learn each other's states and then update their states based on what they learned. We present the Circles protocol that solves the relative majority problem with k3 states. It is always-correct under weakly fair scheduling. Not only does it improve upon the best known upper bound of O(k7), but it also shows a strikingly simpler design inspired by energy minimization in chemical settings.}, author = {Breitkopf, Tom-Lukas and Dallot, Julien and El-Hayek, Antoine and Schmid, Stefan}, booktitle = {Proceedings of the ACM Symposium on Principles of Distributed Computing}, isbn = {9798400718854}, location = {Huatulco, Mexico}, pages = {549--552}, publisher = {Association for Computing Machinery}, title = {{Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols}}, doi = {10.1145/3732772.3733512}, year = {2025}, } @inproceedings{18557, abstract = {Broadcast and Consensus are most fundamental tasks in distributed computing. These tasks are particularly challenging in dynamic networks where communication across the network links may be unreliable, e.g., due to mobility or failures. Over the last years, researchers have derived several impossibility results and high time complexity lower bounds for these tasks. Specifically for the setting where in each round of communication the adversary is allowed to choose one rooted tree along which the information is disseminated, there is a lower as well as an upper bound that is linear in the number n of nodes for Broadcast and for n ≥ 3 the adversary can guarantee that Consensus never happens. This setting is called the oblivious message adversary for rooted trees. Also note that if the adversary is allowed to choose a graph that does not contain a rooted tree, then it can guarantee that Broadcast and Consensus will never happen. However, such deterministic adversarial models may be overly pessimistic, as many processes in real-world settings are stochastic in nature rather than worst-case. This paper studies Broadcast on stochastic dynamic networks and shows that the situation is very different to the deterministic case. In particular, we show that if information dissemination occurs along random rooted trees and directed Erdős–Rényi graphs, Broadcast completes in O(log n) rounds of communication with high probability. The fundamental insight in our analysis is that key variables are mutually independent. We then study two adversarial models, (a) one with Byzantine nodes and (b) one where an adversary controls the edges. (a) Our techniques without Byzantine nodes are general enough so that they can be extended to Byzantine nodes. (b) In the spirit of smoothed analysis, we introduce the notion of randomized oblivious message adversary, where in each round, an adversary picks k ≤ 2n/3 edges to appear in the communication network, and then a graph (e.g. rooted tree or directed Erdős–Rényi graph) is chosen uniformly at random among the set of all such graphs that include these edges. We show that Broadcast completes in a finite number of rounds, which is, e.g., O(k+log n) rounds in rooted trees. We then extend these results to All-to-All Broadcast, and Consensus, and give lower bounds that show that most of our upper bounds are tight.}, author = {El-Hayek, Antoine and Henzinger, Monika H and Schmid, Stefan}, booktitle = {38th International Symposium on Distributed Computing}, isbn = {9783959773522}, issn = {1868-8969}, location = {Madrid, Spain}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges}}, doi = {10.4230/LIPIcs.DISC.2024.21}, volume = {319}, year = {2024}, }