In this paper, we consider dynamic matroids, where elements can be inserted to or deleted from the ground set over time. The independent sets change to reflect the current ground set. As matroids are central to the study of many combinatorial optimization problems, it is a natural next step to also consider them in a dynamic setting. The study of dynamic matroids has the potential to generalize several dynamic graph problems, including, but not limited to, arboricity and maximum bipartite matching. We contribute by providing efficient algorithms for some fundamental matroid questions. In particular, we study the most basic question of maintaining a base dynamically, providing an essential building block for future algorithms. We further utilize this result and consider the elementary problems of base packing and base covering. We provide a deterministic algorithm that maintains a (1± ε)-approximation of the base packing number Φ in O(Φ ⋅ poly(log n, ε^{-1})) queries per update. Similarly, we provide a deterministic algorithm that maintains a (1± ε)-approximation of the base covering number β in O(β ⋅ poly(log n, ε^{-1})) queries per update. Moreover, we give an algorithm that maintains a (1± ε)-approximation of the base covering number β in O(poly(log n, ε^{-1})) queries per update against an oblivious adversary. These results are obtained by exploring the relationship between base collections, a generalization of tree-packings, and base packing and covering respectively. We provide structural theorems to formalize these connections, and show how they lead to simple dynamic algorithms.

As the main contribution of this work we present deterministic edge coloring algorithms in the CONGEST model. In particular, we present an algorithm that edge colors any n-node graph with maximum degree Δ with (1+ε)Δ+O(log⁡n) colors in Õ(log2.5 n + log2 Δ log n) rounds. This brings the upper bound polynomially close to the lower bound of Ω(log n/log log n) rounds that also holds in the more powerful LOCAL model [Chang, He, Li, Pettie, Uitto; SODA'l8]. As long as Δ≥clog⁡n our algorithm uses fewer than 2Δ - 1 colors and to the best of our knowledge is the first polylogarithmic-round CONGEST algorithm achieving this for any range of Δ.

We give new, improved bounds for approximating the sparsest cut value or in other words the conductance $$\phi $$ of a graph in the $$\textsf{CONGEST}$$ model. As our main result, we present an algorithm running in $$O(\log ^2 n/\phi )$$ rounds in which every vertex outputs a value $$\tilde{\phi }$$ satisfying $$\phi \le \tilde{\phi }\le \sqrt{2.01\phi }$$ . In most regimes, our algorithm improves significantly over the previously fastest algorithm for the problem [Chen, Meierhans, Probst Gutenberg, Saranurak; SODA 25]. Additionally, our result generalizes to k-way conductance. We obtain these results, by approximating the eigenvalues of the normalized Laplacian matrix $$L:=I-{{\,\textrm{Deg}\,}}^{-1/2}A{{\,\textrm{Deg}\,}}^ {-1/2}$$ , where, A is the adjacency matrix and $${{\,\textrm{Deg}\,}}$$ is the diagonal matrix with the weighted degrees on the diagonal. We show our algorithms are near-optimal by proving a lower bound for computing the smallest non-trivial eigenvalue of L, even in the stronger LOCAL model. The previous state of the art sparsest cut algorithm is in the technical realm of expander decompositions. Our algorithms, on the other hand, are relatively simple and easy to implement. At the core, they rely on the well-known power method, which comes down to repeatedly multiplying the Laplacian with a vector. This operation can be performed in a single round in the $$\textsf{CONGEST}$$ model. All our algorithms apply to weighted, undirected graphs. Our lower bounds apply even in unweighted graphs. Full version: https://arxiv.org/abs/2508.19898 .

In this paper, we provide the first deterministic algorithms with sublogarithmic round complexity for spanners and approximate shortest paths in various MPC models. Moreover, we significantly improve upon the state of the art in the deterministic Congested Clique. In particular, we obtain the following four results on undirected graphs:

Abstract Tree-packings – collections of spanning trees of a graph – are a fundamental tool in the study of minimum cut and related graph parameters. They have played a central role in the design of algorithms across static, dynamic, and distributed settings. In this paper, we study both tree-packings themselves and their structural connections to min-cut and arboricity. Our results lead to faster dynamic algorithms for both problems. For dynamic min-cut, [Thorup, Comb. 2007] used tree-packings to obtain his dynamic min-cut algorithm with $$\tilde{O}(\lambda ^{14.5}\sqrt{n})$$ O ~ ( λ 14.5 n ) worst-case update time. We reexamine this relationship, showing that we need to maintain fewer trees for such a result; we show that we only need to pack $$\Theta (\lambda ^3 \log m)$$ Θ ( λ 3 log m ) greedy trees to guarantee either a 1-respecting cut or a trivial cut in some contracted graph. Based on this structural result, we then provide a deterministic algorithm for fully dynamic exact min-cut that has $$\tilde{O}(\lambda ^{5.5}\sqrt{n})$$ O ~ ( λ 5.5 n ) worst-case update time, for graphs with min-cut value at most $$\lambda $$ λ . In particular, this also yields an algorithm for fully dynamic exact min-cut with $$\tilde{O}(m^{1-1/12})$$ O ~ ( m 1 - 1 / 12 ) amortized update time, improving upon $$\tilde{O}(m^{1-1/31})$$ O ~ ( m 1 - 1 / 31 ) [Goranci et al., SODA 2023]. We also give the first fully dynamic algorithm that maintains a $$(1+\varepsilon )$$ ( 1 + ε ) -approximation of the fractional arboricity. Our algorithm is deterministic and has $$O(\alpha \log ^6m/\varepsilon ^4)$$ O ( α log 6 m / ε 4 ) amortized update time, for graphs with arboricity at most $$\alpha $$ α

A tree-packing is a collection of spanning trees of a graph. It has been a useful tool for computing the minimum cut in static, dynamic, and distributed settings. In particular, [Thorup, Comb. 2007] used them to obtain his dynamic min-cut algorithm with worst-case update time. We reexamine this relationship, showing that we need to maintain fewer spanning trees for such a result; we show that we only need to pack Θ(λ3 log m ) greedy trees to guarantee a 1-respecting cut or a trivial cut in some contracted graph. Based on this structural result, we then provide a deterministic algorithm for fully dynamic exact min-cut, that has worst-case update time, for min-cut value bounded by λ. In particular, this also leads to an algorithm for general fully dynamic exact min-cut with amortized update time, improving upon Õ (m 1-1/31 ) [Goranci et al., SODA 2023]. We also give the first fully dynamic algorithm that maintains a (1 + ε )-approximation of the fractional arboricity - which is strictly harder than the integral arboricity. Our algorithm is deterministic and has O (α log6 m/ε 4) amortized update time, for arboricity at most a. We extend these results to a Monte Carlo algorithm with O (poly(log m, ε -1)) amortized update time against an adaptive adversary. Our algorithms work on multi-graphs as well. Both result are obtained by exploring the connection between the min-cut/arboricity and (greedy) tree-packing. We investigate tree-packing in a broader sense; including a lower bound for greedy treepacking, which – to the best of our knowledge – is the first progress on this topic since [Thorup, Comb. 2007].

For n -vertex m -edge graphs with integer polynomially-bounded costs and capacities, we provide a randomized parallel algorithm for the minimum cost flow problem with \(\tilde{O}(m+n^ {1.5}) \) work and \(\tilde{O}(\sqrt {n}) \) depth. On moderately dense graphs ( m > n 1.5 ), our algorithm is the first one to achieve both near-linear work and sub-linear depth. Previous algorithms are either achieving almost optimal work but are highly sequential [18], or achieving sub-linear depth but use super-linear work [49, 62]. Our result also leads to improvements for the special cases of max flow, bipartite maximum matching, shortest paths, and reachability. Notably, the previous algorithms achieving near-linear work for shortest paths and reachability all have depth \(n^{o(1)}\cdot \sqrt {n} \) [26, 33]. Our algorithm consists of a parallel implementation of [11]. One important building block is a parallel batch-dynamic expander decomposition, which we show how to obtain from the recent parallel expander decomposition of [17]. Other versions. An extended abstract of this paper was previously published in the Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2025.

We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with m edges and n nodes undergoing edge deletions, we provide four new approximate decremental APSP algorithms, two for weighted and two for unweighted graphs. Our first result is (2 + ϵ)-APSP with total update time Õ(m1/2n3/2) (when m = n1+c for any constant 0 < c < 1). Prior to our work the fastest algorithm for weighted graphs with approximation at most 3 had total Õ(mn) update time for (1 + ϵ)-APSP [Bernstein, SICOMP 2016]. Our second result is (2 + ϵ, Wu,v)-APSP with total update time Õ(nm3/4), where the second term is an additive stretch with respect to Wu,v, the maximum weight on the shortest path from u to v. Our third result is (2 + ϵ)-APSP for unweighted graphs in Õ(m7/4) update time, which for sparse graphs (m = o(n8/7)) is the first subquadratic (2 + ϵ)-approximation. Our last result for unweighted graphs is (1 + ϵ, 2(k − 1))-APSP, for k ≥ 2, with Õ(n2−1/km1/k) total update time (when m = n1+c for any constant c > 0). For comparison, in the special case of (1 + ϵ, 2)-approximation, this improves over the state-of-the-art algorithm by [Henzinger, Krinninger, Nanongkai, SICOMP 2016] with total update time of Õ(n2.5). All of our results are randomized, work against an oblivious adversary, and have constant query time.

In this paper, we revisit the classic approximate All-Pairs Shortest Paths (APSP) problem in undirected graphs. For unweighted graphs, we provide an algorithm for 2-approximate APSP in Õ(n2.5-r + nω(r)) time, for any r ∈ [0,1]. This is O(n2.032) time, using known bounds for rectangular matrix multiplication nω(r) [Le Gall, Urrutia, SODA 2018]. Our result improves on the Õ(n2·25) bound of [Roditty, STOC 2023], and on the bound of [Baswana, Kavitha, SICOMP 2010] for graphs with m ≥ n1·532 edges.

In this paper, we bring the techniques of the Laplacian paradigm to the congested clique, while further restricting ourselves to deterministic algorithms. In particular, we show how to solve a Laplacian system up to precision ϵ in no(1) log(1/ϵ) rounds. We show how to leverage this result within existing interior point methods for solving flow problems. We obtain an m3/7+o(1) U1/7 round algorithm for maximum flow on a weighted directed graph with maximum weight U, and we obtain an Õ(m3/7(n0.158 + no(1) poly log W)) round algorithm for unit capacity minimum cost flow on a directed graph with maximum cost W. Hereto, we give a novel routine for computing Eulerian orientations in O(log n log* n) rounds, which we believe may be of separate interest.

We consider the CONGEST model on a network with n nodes, m edges, diameter D, and integer costs and capacities bounded by poly n. In this paper, we show how to find an exact solution to the minimum cost flow problem in n1/2+o(1)(√n + D) rounds, improving the state of the art algorithm with running time m3/7+o(1)(√nD1/4 + D)[13], which only holds for the special case of unit capacity graphs. For certain graphs, we achieve even better results. In particular, for planar graphs, expander graphs, no(1)-genus graphs, no(1)-treewidth graphs, and excluded-minor graphs our algorithm takes n1/2+o(1) D rounds. We obtain this result by combining recent results on Laplacian solvers in the CONGEST model [2, 13] with a CONGEST implementation of the LP solver of Lee and Sidford [22], and finally show that we can round the approximate solution to an exact solution. Our algorithm solves certain linear programs, that generalize minimum cost flow, up to additive error ϵ in n1/2+o(1)(√n + D)log3(1/ϵ) rounds.

Abstract A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of $$(1\pm \epsilon )$$ ( 1 ± ϵ ) . This paper considers computing cut sparsifiers of weighted graphs of size $$O(n\log (n)/\epsilon ^2)$$ O ( n log ( n ) / ϵ 2 ) . Our algorithm computes such a sparsifier in time $$O(m\cdot \min (\alpha (n)\log (m/n),\log (n)))$$ O ( m · min ( α ( n ) log ( m / n ) , log ( n ) ) ) , both for graphs with polynomially bounded and unbounded integer weights, where $$\alpha (\cdot )$$ α ( · ) is the functional inverse of Ackermann’s function. This improves upon the state of the art by Benczúr and Karger (SICOMP, 2015), which takes $$O(m\log ^2 (n))$$ O ( m log 2 ( n ) ) time. For unbounded weights, this directly gives the best known result for cut sparsification. Together with preprocessing by an algorithm of Fung et al. (SICOMP, 2019), this also gives the best known result for polynomially-weighted graphs. Consequently, this implies the fastest approximate min-cut algorithm, both for graphs with polynomial and unbounded weights. In particular, we show that it is possible to adapt the state of the art algorithm of Fung et al. for unweighted graphs to weighted graphs, by letting the partial maximum spanning forest (MSF) packing take the place of the Nagamochi–Ibaraki forest packing. MSF packings have previously been used by Abraham et al. (FOCS, 2016) in the dynamic setting, and are defined as follows: an M-partial MSF packing of G is a set $$\mathcal {F}=\{F_1, \ldots , F_M\}$$ F = { F 1 , … , F M } , where $$F_i$$ F i is a maximum spanning forest in $$G{\setminus } \bigcup _{j=1}^{i-1}F_j$$ G \ ⋃ j = 1 i - 1 F j . Our method for computing (a sufficient estimation of) the MSF packing is the bottleneck in the running time of our sparsification algorithm.

A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of $(1\pmε)$. This paper considers computing cut sparsifiers of weighted graphs of size $O(n\log (n)/ε^2)$. Our algorithm computes such a sparsifier in time $O(m\cdot\min(α(n)\log(m/n),\log (n)))$, both for graphs with polynomially bounded and unbounded integer weights, where $α(\cdot)$ is the functional inverse of Ackermann's function. This improves upon the state of the art by Benczúr and Karger (SICOMP 2015), which takes $O(m\log^2 (n))$ time. For unbounded weights, this directly gives the best known result for cut sparsification. Together with preprocessing by an algorithm of Fung et al. (SICOMP 2019), this also gives the best known result for polynomially-weighted graphs. Consequently, this implies the fastest approximate min-cut algorithm, both for graphs with polynomial and unbounded weights. In particular, we show that it is possible to adapt the state of the art algorithm of Fung et al. for unweighted graphs to weighted graphs, by letting the partial maximum spanning forest (MSF) packing take the place of the Nagamochi-Ibaraki (NI) forest packing. MSF packings have previously been used by Abraham at al. (FOCS 2016) in the dynamic setting, and are defined as follows: an $M$-partial MSF packing of $G$ is a set $\mathcal{F}=\{F_1, \dots, F_M\}$, where $F_i$ is a maximum spanning forest in $G\setminus \bigcup_{j=1}^{i-1}F_j$. Our method for computing (a sufficient estimation of) the MSF packing is the bottleneck in the running time of our sparsification algorithm.

The Quantum CONGEST model is a variant of the CONGEST model, where messages consist of O(log(n)) qubits. In this paper, we give a general framework for implementing quantum query algorithms efficiently in a Quantum CONGEST network, using the concept of parallel-query quantum algorithms.

In this paper, we bring the main tools of the Laplacian paradigm to the Broadcast Congested Clique. We introduce an algorithm to compute spectral sparsifiers in a polylogarithmic number of rounds, which directly leads to an efficient Laplacian solver. Based on this primitive, we consider the linear program solver of Lee and Sidford [30].

Spanners have been shown to be a powerful tool in graph algorithms. Many spanner constructions use a certain type of clustering at their core, where each cluster has small diameter and there are relatively few spanner edges between clusters. In this paper, we provide a clustering algorithm that, given $k\geq 2$, can be used to compute a spanner of stretch $2k-1$ and expected size $O(n^{1+1/k})$ in $k$ rounds in the CONGEST model. This improves upon the state of the art (by Elkin, and Neiman [TALG'19]) by making the bounds on both running time and stretch independent of the random choices of the algorithm, whereas they only hold with high probability in previous results. Spanners are used in certain synchronizers, thus our improvement directly carries over to such synchronizers. Furthermore, for keeping the \emph{total} number of inter-cluster edges small in low diameter decompositions, our clustering algorithm provides the following guarantees. Given $β\in (0,1]$, we compute a low diameter decomposition with diameter bound $O\left(\frac{\log n}β\right)$ such that each edge $e\in E$ is an inter-cluster edge with probability at most $β\cdot w(e)$ in $O\left(\frac{\log n}β\right)$ rounds in the CONGEST model. Again, this improves upon the state of the art (by Miller, Peng, and Xu [SPAA'13]) by making the bounds on both running time and diameter independent of the random choices of the algorithm, whereas they only hold with high probability in previous results.