New limits on memory versus speed for dynamic graph connectivity

Connectivity in a New Bounded-Space Dynamic Model

Data Structures and Algorithms

Summary

Finding out if two points are connected in a changing network usually gets faster if the computer uses more memory. This paper studies how well algorithms can do when they have only a small, fixed workspace and read-only access to the network, which keeps changing by adding or removing links. The authors find lower bounds on how much time it takes to update connectivity info depending on memory size and how the network is accessed, showing that if memory is limited, the updates must take much longer. Their results show a tradeoff: less memory means slower dynamic graph algorithms even for simple cases.

What this means in practice

  • For database engineers: Design dynamic graph query systems constrained by limited memory, knowing update speed cannot be improved beyond certain bounds.
  • For network protocol designers: Understand inherent delays in dynamic connectivity checks when device memory is severely limited for routing decisions.

A theory result. No direct application yet.

Authors

Bardiya Aryanfard, Monika Henzinger, John Kuszmaul, Jakob Nogler, Virginia Vassilevska Williams

Abstract

We introduce a new model for dynamic algorithms in which the algorithm has read-only oracle access to a dynamically changing input and random access to its own bounded workspace. It is a dynamic analogue of the time-space tradeoffs for static inputs studied in complexity theory, where only writable memory counts as space. We study dynamic undirected $s$-$t$ connectivity: after every edge update to an $n$-vertex graph, an algorithm with $S$ words of workspace must report whether $s$ and $t$ are connected. The graph is accessed via adjacency list queries (degree, $j$-th neighbor) or adjacency matrix queries. Our algorithms are randomized; our lower bounds hold for randomized algorithms with $cn$ bits of workspace, $c>0$ a small constant ($cn/\log n$ for the worst-case matrix bound). We prove: (1) With adjacency lists, worst-case time $\tildeΘ(n^2/S^2)$ per insertion is necessary and sufficient for incremental algorithms. (2) With an adjacency matrix, worst-case time $\tildeΩ(n^2/S)$ per insertion is necessary for incremental algorithms, and sufficient for $S\ge\sqrt{n}$. (3) With amortization, incremental algorithms achieve $\tilde O(n/S)$ time per insertion with adjacency lists and $\tilde O(n^2/S)$ with an adjacency matrix, while $\tildeΩ(\sqrt{n/S})$ and $\tildeΩ(n\sqrt{n/S})$, respectively, are necessary. (4) Fully dynamic algorithms need amortized time $\tildeΩ(n/S)$ per update with adjacency lists and $\tildeΩ(n^2/S)$ with an adjacency matrix, even on forests, where both bounds are tight (lists: under bounded degree). Conventional dynamic connectivity admits polylogarithmic update time with $Ω(n)$ words of space. In contrast, our lower bounds show that polynomial update time is necessary whenever $S\le n^{1-\varepsilon}$, even for a single pair of vertices and even for incremental algorithms with amortized guarantees.