Connectivity in a New Bounded-Space Dynamic Model

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 Θ(n²/S²) per insertion is necessary and sufficient for incremental algorithms. (2) With an adjacency matrix, worst-case time Ω(n²/S) per insertion is necessary for incremental algorithms, and sufficient for S≥√n. (3) With amortization, incremental algorithms achieve O(n/S) time per insertion with adjacency lists and O(n²/S) with an adjacency matrix, while Ω(√n/S) and Ω(n√n/S), respectively, are necessary. (4) Fully dynamic algorithms need amortized time Ω(n/S) per update with adjacency lists and Ω(n²/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≤ n1-ε, even for a single pair of vertices and even for incremental algorithms with amortized guarantees.