Dynamic Graph Algorithms

This talk is a discussion on exciting recent progress in distributed subgraph finding (static and dynamic) and describing some of the many intriguing open questions.

In this work we prove conditional lower bounds against approximate distance oracles in static and dynamic settings. The seminal Thorup-Zwick distance oracles achieve stretch $2k\pm O(1)$ after preprocessing a graph in $O(m{n}^{1/k})$ time. For the same stretch, and assuming the query time is $n^{o(1)}$, Abboud, Bringmann, Khoury and Zamir (STOC ’22) proved an $\mathrm{\Omega }(m^{1+\frac{1}{12.7552\cdot k}})$ lower bound on the preprocessing time; we improve it to $\mathrm{\Omega }(m^{1+1/2k})$ which is only a factor $2$ away from the upper bound. Additionally, we obtain tight bounds for stretch $3-ϵ$ and higher lower bounds for dynamic shortest paths.

We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylogarithmic amortized update time and answers queries for the distance between any pair of vertices in the current graph with a polylogarithmic approximation in $O(\log \log n)$ time.

Prior to this work, no data structure was known for partially dynamic graphs, i.e., graphs undergoing either edge insertions or deletions, with less than $n^{o(1)}$ update time except for dense graphs, even when allowing randomization against oblivious adversaries or considering only single-source distances.

We show a $(1+ϵ)$-approximation algorithm for maintaining maximum $s$-$t$ flow under $m$ edge insertions in $m^{1/2+o(1)}{ϵ}^{-1/2}$ amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm in general sparse graphs with arbitrarily good approximation guarantee.

Fully dynamic graph algorithms have received growing attention in experimental work recently, though still by far not as much as they have in theory. In this talk, we will consider different approaches to maintain reachability information in a graph as it undergoes a series of insertions and deletions and analyze their behavior in practice on different types of fully dynamic instances.

The study of fully dynamic algorithms in practice is complicated by a lack of real-world, “real-dynamic” instances that are available publicly. In this talk will take a closer look at how the characteristics of an update sequence can influence the behavior of dynamic algorithms for reachability and subgraph counting and also review different approaches that are currently in use to overcome the shortage in fully dynamic instances in practice.

The talk concludes with a summary of lessons learned when engineering specifically dynamic graph algorithms.

A relatively small portion of the known dynamic algorithms for shortest paths and related problems have strongly polynomial update bounds. This means, roughly speaking, that in most cases the update bounds either do not hold for real-weighted graphs or depend on the magnitude of the graph’s weights. One notable exception is the fully dynamic APSP algorithm of Demetrescu and Italiano [J.ACM’04].

In this talk, we will consider maintaining negative/minimum-weight/minimum-mean cycles in dynamic real-weighted digraphs. The best-known static strongly polynomial algorithms for these classical problems run in $O(nm)$ time. For some of these problems, non-trivial strongly polynomial update bounds can be obtained. For others, we will try to identify some challenges.

In the dynamic linear program (LP) problem, we are given an LP undergoing updates and we need to maintain an approximately optimal solution. Recently, significant attention (e.g., [Gupta et al. STOC’17; Arar et al. ICALP’18, Wajc STOC’20]) has been devoted to the study of special cases of dynamic packing and covering LPs, such as the dynamic fractional matching and set cover problems. But until now, there is no non-trivial dynamic algorithm for general packing and covering LPs. In this work, we settle the complexity of dynamic packing and covering LPs, up to a polylogarithmic factor in update time. More precisely, in the partially dynamic setting (where updates can either only relax or only restrict the feasible region), we give near-optimal deterministic $ϵ$-approximation algorithms with polylogarithmic amortized update time. Then, we show that both partially dynamic updates and amortized update time are necessary; without any of these conditions, the trivial algorithm that recomputes the solution from scratch after every update is essentially the best possible, assuming SETH. To obtain our results, we initiate a systematic study of the multiplicative weights update (MWU) method in the dynamic setting. As by-products of our techniques, we also obtain the first online $(1+ϵ)$-competitive algorithms for both covering and packing LPs with polylogarithmic recourse, and the first streaming algorithms for covering and packing LPs with linear space and polylogarithmic passes.

In the 2-choice allocation problem, $m$ balls are placed into $n$ bins, and each ball must choose between two random bins $i,j\in [n]$ that it has been assigned to. It has been known for more than two decades, that if each ball follows the Greedy strategy (i.e., always pick the less-full bin), then the maximum load will be $m/n+O(\log \log n)$ with high probability in $n$ (and $m/n+O(\log m)$ with high probability in $m$). It has remained an open question whether the same bounds hold in the dynamic version of the same game, where balls are inserted/deleted with no more than $m$ balls present at a time.

We show that, somewhat surprisingly, these bounds do not hold in the dynamic setting: already on $4$ bins, there exists a sequence of insertions/deletions that cause the Greedy strategy to incur a maximum load of $m/4+\mathrm{\Omega }(\sqrt{m})$ with probability $\mathrm{\Omega }(1)$, This raises the question of whether any 2-choice allocation strategy can offer a strong bound in the dynamic setting. Our second result answers this question in the affirmative: we present a new strategy, called ModulatedGreedy, that guarantees a maximum load of $m/n+O(\log m)$, at any given moment, with high probability in $m$.

We show an algorithm for decremental maintenance of connected components and 2-edge connected components , which handles any sequence of edge deletions in $O(m+n\mathrm{polylog}n)$ time and answers queries in constant time. This talk focuses on three ideas behind this result: a new sparse connectivity certificate, which can be updated dynamically, a new way of using the XOR-trick, which allows one detect small cuts, and a self-check technique, which allows us to obtain a Las Vegas randomized algorithm based on a Monte Carlo data structure.

Online optimization refers to solving problems where an initially unknown input is revealed incrementally, and irrevocable decisions must be made not knowing future requests. The assumption of not having any prior knowledge about future requests seems overly pessimistic. Given the success of machine-learning methods and data-driven applications, one may expect to have access to predictions about future requests. However, simply trusting them might lead to very poor solutions as these predictions come with no quality guarantee. In this talk we present recent developments in the young line of research that integrates such error-prone predictions into algorithm design to break through worst case barriers. We discuss algorithmic challenges with a focus on online routing and network design and present algorithms with performance guarantees depending on a novel error metric.

The first part of the talk focuses on our deterministic fully dynamic algorithms for computing approximate distances in a graph. Specifically, we are given an unweighted and undirected graph $G=(V,E)$ undergoing edge insertions and deletions, and a parameter , and our goal is to maintain $(1+ϵ)$-approximate distances between a single pair (st distance), a single source to all nodes (SSSP), or all pairs (APSP). We discuss how combinatorial tools such as emulators can be combined with algebraic data structures to obtain deterministic algorithms with improved worst-case guarantees for these problems.

The second part of the talk focuses on future directions for obtaining improved fully dynamic algorithms for weighted or directed graphs. We explore possible candidate combinatorial structures that could be used and the challenges in maintaining them in the fully dynamic settings.

In this talk we discuss insights from the development of a scalable system for processing dynamic graph algorithms with low latency inside Google. We discuss applications, requirements, and challenges that arise in such a real-world system. The three challenges that we discuss are 1) how to maintain a solution that does not change very drastically during the execution of the algorithm, 2) how to process a graph in a distributed and dynamic fashion; which is mandated by the scale of the data, and 3) how to process a large volume of concurrent updates, each within low latency. These challenges naturally lead us in exploring new models (and evaluating the suitability of existing models) for tackling them.

This talk is a tutorial on how to use differential privacy to obtain a black-box reduction that can transform any dynamic algorithm for any estimation problem that works against an oblivious adversary to another algorithm against an adaptive adversary.

In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this talk, we give a brief overview of results in engineering dynamic graph algorithms that we achieved recently. To this end, we give a high level overview of dynamic algorithms and their performance for (hyper) graph ($b$-)matching, independent sets, edge-orientation, reachability as well as $k$-center clustering and minimum cuts.

The requirement of social distancing during the COVID-19 pandemic has presented significant challenges for high-rise buildings, which heavily rely on elevators for vertical transportation. In particular, the need for social distancing has reduced elevator capacity typically by at least two-thirds or as much as over 90% the normal amount. This reduction is a serious concern, as reduced elevator capacities cause large queues to build up in lobbies, which makes social distancing difficult and results in large wait times. The objective of this study is to safely manage the elevator queues by proposing simple, technology-free interventions that drastically reduce the waiting time and length of lobby queues. We use mathematical modeling, epidemiological expertise, and simulation to design and evaluate our interventions. The key idea is to explicitly or implicitly group passengers that are going to the same floor into the same elevator as much as possible. In the Cohorting intervention, we attempt to find passengers going to the same floor as the first person in the queue. In the Queue Splitting intervention, we create a different queue for different groups of floors. Based on simulation and analytical findings, Cohorting and Queue Splitting can significantly reduce queue length and wait time, while also maintaining safety from viral transmission in otherwise crowded elevators, building lobbies, and entrances. These interventions are generally accessible for many buildings since they do not require programming the elevators, and rely on only using signage and/or a queue manager to guide passengers.

Existing graph stream processing systems must store the graph explicitly in RAM which limits the scale of graphs they can process. The graph semi-streaming literature offers algorithms which avoid this limitation via linear sketching data structures that use small (sublinear) space, but these algorithms have not seen use in practice to date.This talk explores what is needed to make graph sketching algorithms practically useful, and as a case study present a sketching algorithm for connected components and a corresponding high-performance implementation. Finally, we give an overview of the many open problems in this area, focusing on improving query performance of graph sketching algorithms.

We present dynamic algorithms with polylog update time for the value version of the dynamic matching problem with approximation ratio strictly better than 2. Specifically, we obtain a $1+1/\sqrt{2}+ϵ\approx 1.707+ϵ$ approximation in bipartite graphs and a $1.973+ϵ$ approximation in general graphs.

A distance oracle is a data structure for answering distance queries on a graph. While on general graphs efficient distance oracles must settle for approximate answers, on planar graphs recent progress has lead to exact oracles with almost linear space and polylogarithmic query time (i.e. almost optimal). However, in the dynamic setting (when the underlying graph is subject to updates) there has been no significant progress in recent years. The state of the art is an exact oracle from more than 20 years ago that given a planar graph supports both updates and queries in $\tilde{O}(n^{2/3})$ time. On the lower-bound side, conditioned on the APSP hypothesis, in any dynamic exact distance oracle (in fact, even in the offline setting) either the update or the query must take $\mathrm{\Omega }(n^{1/2})$ time, leaving an intriguing gap. For approximate distances, the currently fastest oracle requires $\tilde{O}(n^{1/2})$ time for both updates and queries (and there is no known lower bound), and in the offline setting there is an almost optimal solution with polylogarithmic time for both updates and queries. In this talk we will describe these upper and lower bounds (for exact distances), the tight connections in planar graphs between distance oracles and maximum-flow (or minimum-cut) oracles, concrete open problems, and possible directions for solving them.

A resizable array is an array that can grow and shrink by the addition or removal of items from its end, or both its ends, while still supporting constant-time access to each item stored in the array given its index. Since the size of an array, i.e., the number of items in it, varies over time, space-efficient maintenance of a resizable array requires dynamic memory management. A standard doubling technique allows the maintenance of an array of size $N$ using only $O(N)$ space, with $O(1)$ amortized time, or even $O(1)$ worst-case time, per operation. Sitarski and Brodnik et al. describe much better solutions that maintain a resizable array of size $N$ using only $N+O(\sqrt{N})$ space, still with $O(1)$ time per operation. Brodnik et al. give a simple proof that this is best possible.

We distinguish between the space needed for storing a resizable array, and accessing its items, and the temporary space that may be needed while growing or shrinking the array. For every integer $r\ge 2$, we show that $N+O(N^{1/r})$ space is sufficient for storing and accessing an array of size $N$, if $N+O(N^{1-1/r})$ space can be used briefly during grow and shrink operations. Accessing an item by index takes $O(1)$ worst-case time while grow and shrink operations take $O(r)$ amortized time. Using an exact analysis of a growth game, we show that for any data structure from a wide class of data structures that uses only $N+O(N^{1/r})$ space to store the array, the amortized cost of grow is $\mathrm{\Omega }(r)$, even if only grow and access operations are allowed. The time for grow and shrink operations cannot be made worst-case, unless $r=2$.

In dynamic unweighted matching, the goal is to maintain an (approximate) maximum cardinality matching in a graph that is changing over time. There is an extensive literature on this problem, with many different state-of-the-art results; these achieve different approximation-ratio/update-time tradeoffs, and also vary on secondary parameters (e.g. worst-case vs. amortized, adaptive vs. oblivious adversary, fully dynamic vs. decremental vs. incremental).

For almost all of these trade-offs, the state-of-the-art for maximum weighted matching lags far behind that for unweighted matching. One could try to adapt each unweighted algorithm separately to the weighted case, but it would be nice to have a single all-purpose tool.

There has been some partial progress in this direction. In 2017, Stubbs and Vassilevska Williams showed how to transform any algorithm for unweighted matching into one for weighted matching, but at the cost of a $(1/2-ϵ)$ approximation [2]. In 2021, Bernstein, Dudeja, and Langley reduced the approximation overhead to $2/3--ϵ$ in non-bipartite graphs and $1-ϵ$ in bipartite graphs [1]. That is, in bipartite graphs, this paper shows a black-box conversion from any algorithm for unweighted matching to one for weighted matching that is essentially as good: the approximation guarantee reduces by $1-ϵ$, while the update time increases by $\log (W)$. Moreover, this transformation preserves all secondary parameters (worst-case, deterministic, etc.); it also works in multiple other models (e.g. streaming, MPC).

The above algorithm gives us a blueprint for the kind of result we would like, but it only works in bipartite graphs. (In non-bipartite graphs the approximation overhead is $3/2$, which in matching is a big drawback.) Is it possible to get a similar transformation in non-bipartite graphs?