Graph Algorithms: Distributed Meets Dynamic

In metric $k$-clustering, we are given as input a set of $n$ points in a general metric space, and we have to pick $k$ centers and cluster the input points around these chosen centers, so as to minimize an appropriate objective function. In recent years, significant effort has been devoted to the study of metric $k$-clustering problems in a dynamic setting, where the input keeps changing via updates (point insertions/deletions), and we have to maintain a good clustering throughout these updates [Fichtenberger, Lattanzi, Norouzi-Fard and Svensson, SODA’21; Bateni, Esfandiari, Fichtenberger, Henzinger, Jayaram, Mirrokni and Weise, SODA’23; Lacki, Haeupler, Grunau, Rozhon and Jayaram, SODA’24; Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24; Forster and Skarlatos, SODA’25]. The performance of such a dynamic algorithm is measured in terms of three parameters: (i) Approximation ratio, which signifies the quality of the maintained solution, (ii) Recourse, which signifies how stable the maintained solution is, and (iii) Update time, which signifies the efficiency of the algorithm.

We consider a textbook metric $k$-clustering problem, metric $k$-median, where the objective is the sum of the distances of the points to their nearest centers. We design the first dynamic algorithm for this problem with near-optimal guarantees across all three performance measures (up to a constant factor in approximation ratio, and polylogarithmic factors in recourse and update time). Specifically, we obtain a $O(1)$-approximation algorithm for dynamic metric $k$-median with $\tilde{O}(1)$ recourse and $\tilde{O}(k)$ update time. Prior to our work, the state-of-the-art here was the recent result of [Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24], who obtained $O({ϵ}^{-1})$-approximation ratio with $\tilde{O}(k^{ϵ})$ recourse and $\tilde{O}(k^{1+ϵ})$ update time.

We achieve our results by carefully synthesizing the concept of robust centers introduced in [Fichtenberger, Lattanzi, Norouzi-Fard and Svensson, SODA’21] along with the randomized local search subroutine from [Bhattacharya, Costa, Garg, Lattanzi and Parotsidis, FOCS’24], in addition to several key technical insights of our own.

In this talk, I will present two improvements in deterministic expander routing: (1) an improved round complexity upper bound that nearly matches the state-of-the-art for randomized algorithms, and (2) a smooth tradeoff between preprocessing and routing time, leading to improved upper bounds in distributed subgraph finding. Additionally, as a side result of independent interest, we establish the equivalence between expander routing and sorting, showing that they are reducible to each other up to a polylogarithmic factor in round complexity within the CONGEST model.

In the dynamic metric $k$-median problem, we wish to maintain a set of $k$ centers $S\subseteq V$ in an input metric space $(V,d)$ that gets updated via point insertions/deletions, so as to minimize the objective ${\sum }_{x\in V}{\min }_{y\in S}d(x,y)$. The quality of a dynamic algorithm is measured in terms of its approximation ratio, “recourse” (the number of changes in $S$ per update) and “update time” (the time it takes to handle an update). The ultimate goal in this line of research is to obtain a dynamic $O(1)$ approximation algorithm with $\tilde{O}(1)$ recourse and $\tilde{O}(k)$ update time.

We come arbitrarily close to resolving the main open question on this topic by developing a new framework of randomized local search that is suitable for adaptation in a dynamic setting. For every $ϵ>0$, this gives us a dynamic $k$-median algorithm with $O(1/ϵ)$ approximation ratio, $\tilde{O}(k^{ϵ})$ recourse and $\tilde{O}(k^{1+ϵ})$ update time. This framework also generalizes to dynamic $k$-clustering with ${\mathrm{\ell }}^p$-norm objectives, giving similar bounds for the dynamic $k$-means and a new trade-off for dynamic $k$-center.

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 $\tilde{O}({\lambda }^{14.5}\sqrt{n})$ 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 $\mathrm{\Theta }({\lambda }^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 $\tilde{O}({\lambda }^{5.5}\sqrt{n})$ worst-case update time, for min-cut value bounded by $\lambda$. In particular, this also leads to an algorithm for general fully dynamic exact min-cut with $\tilde{O}(m^{1-1/12})$ amortized update time, improving upon $\tilde{O}(m^{1-1/31})$ [Goranci et al., SODA 2023].

We also give the first fully dynamic algorithm that maintains a $(1+\epsilon )$-approximation of the fractional arboricity – which is strictly harder than the integral arboricity. Our algorithm is deterministic and has $O(\alpha {\log }^{6}m/{\epsilon }^4)$ amortized update time, for arboricity at most $\alpha$. We extend these results to a Monte Carlo algorithm with $O(poly(\log m,{\epsilon }^{-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 tree-packing, which – to the best of our knowledge – is the first progress on this topic since [Thorup, Comb. 2007].

I will discuss a recent work where we show an $O(1)$-approximation algorithm for All-Pairs Shortest Paths, that takes just $O(\log \log \log n)$ rounds in the distributed Congested Clique model, improving exponentially over the state-of-the art. I will describe the main ingredients of the algorithm, that can find applications in other settings, such as dynamic algorithms.

Algorithms with predictions are algorithms that are given extra information about a problem, which may be incorrect. The better the prediction, the more it should help for solving the problem. I will present a framework for evaluating deterministic distributed graph algorithms with predictions, some templates for transforming algorithms in synchronous message passing systems to effectively make use of predictions, and apply it to obtain good distributed algorithms with predictions for the Maximal Independent Set problem.

Mahlmann and Schindelhauer (2005) proposed the following simple process, called flip-chain, for transforming any given connected $d$-regular graph into a $d$-regular expander. In each step, a random $3$-path $abcd$ is selected, and edges $ab$ and $cd$ are replaced by two new edges $ac$ and $bd$, provided that $ac$ and $bd$ do not exist already. A motivation for the study of the flip-chain arises in the design of overlay networks, where it is common practice that adjacent nodes periodically exchange random neighbors, to maintain good connectivity properties. It is known that the flip-chain converges to the uniform distribution over connected $d$-regular graphs, and it was conjectured that an expander graph is obtained after $O(nd\log n)$ steps, w.h.p., where $n$ is the number of vertices. In this talk, we describe a new analysis of a natural flip-chain instantiation, which shows that starting from any connected $d$-regular graph, for $d=\mathrm{\Omega }(\log n)$, an expander is obtained after $O(nd{\log }^{2}n)$ steps, w.h.p.

A recent work by Christiansen, Nowicki, and Rotenberg [STOC’23] provides dynamic algorithms for coloring sparse graphs, concretely as a function of the graph’s arboricity $\alpha$. They give two randomized algorithms: $O(\alpha \log \alpha )$ implicit coloring in $poly(\log n)$ worst-case update and query times, and $O(\min \{\alpha \log \alpha ,\alpha \log \log \log n\})$ implicit coloring in $poly(\log n)$ amortized update and query times (against an oblivious adversary). We improve these results in terms of the number of colors and the time guarantee: First, we present an extremely simple algorithm that computes an $O(\alpha )$-implicit coloring with $poly(\log n)$ amortized update and query times. Second, and as the main technical contribution of our work, we show that the time complexity guarantee can be strengthened from amortized to worst-case. That is, we give a dynamic algorithm for implicit $O(\alpha )$-coloring with $poly(\log n)$ worst-case update and query times (against an oblivious adversary).

We study the problem of dynamically maintaining the connected components of an undirected graph subject to edge insertions and deletions. We give the first parallel algorithm for the problem which supports updates in polylogarithmic time and uses linear space. On the empirical side, we provide the first implementation of the (sequential) cluster forest algorithm. We evaluate it empirically and find that it uses up to 19.7× less space and is up to 6.2× faster than the best existing baseline.

In this talk, we investigate listing cliques of arbitrary sizes in bandwidth-limited, dynamic networks. The problem of detecting and listing triangles and cliques was originally studied in great detail by Bonne and Censor-Hillel [ICALP 2019]. We extend this study to dynamic graphs where more than one update may occur as well as resolve an open question posed by Bonne and Censor-Hillel [2019]. Our algorithms and results are based on some simple observations about listing triangles under various settings and we show that we can list larger cliques using such facts. Specifically, we show that our techniques can be used to solve an open problem posed in the original paper: we show that detecting and listing cliques (of any size) can be done using $O(1)$-bandwidth after one round of communication under node insertions and node/edge deletions. We conclude with an extension of our techniques to obtain a small bandwidth $1$-round algorithm for listing cliques when more than one node insertion/deletion and/or edge deletion update occurs at any time.

Smoothed analysis is a framework suggested for mediating gaps between worst-case and average-case complexities. In the case of dynamic networks, this technique aims to explain the gaps between real-world networks that function well despite being dynamic and the strong theoretical lower bounds for arbitrary networks. In the seminar, I presented our recent applications of smoothed analysis to dynamic networks. Our work studies different models of adversarial behavior and concerns problems such as information propagation and load balancing. Finally, I mentioned our preliminary results regarding applying smoothed analysis to centralized dynamic graph algorithms.

We consider the problem of computing shortest paths in the presence of an edge failure in a graph in a distributed setting. In the sequential context, two versions of this problem have been studied widely: Replacement Paths (RP), where a specific source-destination pair is given, and we need to compute a shortest path in the graph when any one edge fails, and Distance Sensitivity Oracles (DSO), where we need to preprocess the graph in order to efficiently return shortest path information for any source-destination pair, and any failed edge. We present several upper and lower bounds for both of these problems in the distributed CONGEST model, and we pose several open problems for further investigation, especially for DSO.

Details of this work are presented in the following two write-ups:

1. 1.

   Vignesh Manoharan, Vijaya Ramachandran,“Computing replacement paths in the CONGEST model,” SIROCCO 2024, LNCS 14662, pp. 420-437, 2024. https://doi.org/10.1007/978-3-031-60603-8_23

2. 2.

   Vignesh Manoharan, Vijaya Ramachandran, “Distributed distance sensitivity oracles,” arXiv:2411.13728, November 2024, SIROCCO 2025, to appear.

Vizing’s theorem states that any $n$-vertex $m$-edge graph of maximum degree $\mathrm{\Delta }$ can be edge colored using at most $\mathrm{\Delta }+1$ different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in $O(mn)$ time. This was subsequently improved to $\tilde{O}(m\sqrt{n})$ time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985].

Very recently, independently and concurrently, using randomization, this runtime bound was further improved to $\tilde{O}(n^2)$ by [Assadi, 2024] and $\tilde{O}(m{n}^{1/3})$ by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to $\tilde{O}(m{n}^{1/4})$ time by [Bhattacharya, Costa, Solomon and Zhang, 2024]).

In this talk, we present a randomized algorithm that computes a $(\mathrm{\Delta }+1)$-edge coloring in near-linear time – in fact, only $O(m\log \mathrm{\Delta })$ time – with high probability, giving a near-optimal algorithm for this fundamental problem.

I will talk about new, surprising connections between dynamic, online, distributed, and quantum worlds. In ICALP 2023 (https://arxiv.org/abs/2109.06593), we introduced a new model of computing, “online-LOCAL”, which gives a unified perspective for discussing locality in online, dynamic, and sequential graph algorithms. Recently we have discovered that in the context of local graph problems, the randomized version of online-LOCAL is strong enough to capture so-called non-signaling distributions, and as a corollary it is also strong enough to capture distributed quantum algorithms (https://arxiv.org/abs/2403.01903). In our very recent work (https://arxiv.org/abs/2409.13795) we demonstrate the power of this new perspective: if we show that a family of problems has the same locality in classical deterministic LOCAL and randomized online-LOCAL, as a corollary we also get a full characterization of locality in e.g. dynamic and quantum settings.

In this talk, I outline recent progress on dynamic single source shortest paths. The result is based on algebraic methods for maintaining distance information for short paths.

We present the first non-trivial fully dynamic algorithm maintaining exact single-source distances in unweighted graphs. This resolves an open problem stated by Sankowski [COCOON 2005] and van den Brand and Nanongkai [FOCS 2019]. Previous fully dynamic single-source distances data structures were all approximate, but so far, non-trivial dynamic algorithms for the exact setting could only be ruled out for polynomially weighted graphs (Abboud and Vassilevska Williams, [FOCS 2014]). The exact unweighted case remained the main case for which neither a subquadratic dynamic algorithm nor a quadratic lower bound was known.

The relax-and-round framework is one of the most ubiquitous in approximation algorithms. In the active area of dynamic (approximation) algorithms, it has mostly played a key role in advances in dynamic matching. This is explained by a gap in our understanding of the rounding step of this framework in dynamic settings: While numerous general approaches have been used to design dynamic fractional algorithms (solving the relaxation), including the primal-dual method, the multiplicative weights method, congestion balancing and continuous optimization methods, the scope of general dynamic rounding approaches is still limited mostly to (unweighted) matching problems.

In this talk, I will discuss some techniques and ideas relating to dynamic rounding of fractional matchings, based on [ACCSW ICALP18, W STOC20, BK ICALP21, K ITCS22, BKSW SODA23, BKSW STOC24, Dudeja ICALP24, Dudeja arXiv:2402.03068, CST SODA25, BCDLST SODA25]. Time permitting, I will highlight some techniques and tools which should prove useful in designing a more general dynamic rounding toolkit.

Edge coloring is a fundamental graph algorithm problem that has been studied extensively in both distributed and dynamic settings. Vizing’s theorem states that any $n$-vertex $m$-edge graph of maximum degree $\mathrm{\Delta }$ can be edge colored using at most $\mathrm{\Delta }+1$ different colors [Diskret. Analiz, ’64]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in $\tilde{O}(mn)$ time. This was subsequently improved to $\tilde{O}(m\sqrt{n})$, independently by Arjomandi [1982] and by Gabow et al. [1985]. In this talk we present a new algorithm that computes such an edge coloring in $\tilde{O}(m{n}^{1/3})$ time, giving the first polynomial improvement for this fundamental problem in over 40 years.

Let $G=(V,E)$ be a simple, undirected graph with $n$ vertices, $m$ edges and maximum degree $\mathrm{\Delta }$. It was shown by Vizing in 1964 that the graph $G$ can always be edge colored with at most $\mathrm{\Delta }+1$ colors.

In the dynamic setting, we have a fixed set of $n$ vertices $V$, and the graph $G$ evolves over time via a sequence of edge insertions and deletions. We assume that we have some fixed value $\mathrm{\Delta }$ and that the maximum degree of $G$ is at most $\mathrm{\Delta }$ at all times. Our objective is to design an algorithm that explicitly maintains an edge coloring $\chi$ of $G$ at all times and has a small update time, which is the time it takes to update the edge coloring $\chi$ after an edge is either inserted or deleted from the graph $G$.

Dual et al. [SODA’19] showed how to maintain a $(1+ϵ)\mathrm{\Delta }$-edge coloring in $\tilde{O}(poly(1/ϵ))$ update time.

A natural question is whether or not we can improve the dependence on $ϵ$ in the update time. In particular, can we maintain a $(\mathrm{\Delta }+\tilde{O}({\mathrm{\Delta }}^{1--\gamma }))$-edge coloring of a dynamic graph $G$ with $\tilde{O}(1)$ update time, for some $\gamma >0$?

Given a graph with $m$ edges and $n$ vertices, Furer and Raghavachari [1] showed a simple $O(mn)$-time algorithm for computing a spanning tree, whose maximum degree is minimized within +1 additive factor from the optimal bound. Is there a near-linear-time algorithm for computing a spanning tree, whose maximum degree is within $O(1)$ multiplicative factor from the optimal bound.

If a $O(\text{polylog}(n))$ multiplicative factor is allowed, there are many possible approaches to obtain near-linear-time algorithms.