betaFeedback

WorksComputer Science

Connectivity in a New Bounded-Space Dynamic Model

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 ss-tt connectivity: after every edge update to an nn-vertex graph, an algorithm with SS words of workspace must report whether ss and tt are connected. The graph is accessed via adjacency list queries (degree, jj-th neighbor) or adjacency matrix queries. Our algorithms are randomized; our lower bounds hold for randomized algorithms with cncn bits of workspace, c>0c>0 a small constant (cn/log⁡ncn/\log n for the worst-case matrix bound). We prove: (1) With adjacency lists, worst-case time Θ~(n2/S2)\tildeΘ(n^2/S^2) per insertion is necessary and sufficient for incremental algorithms. (2) With an adjacency matrix, worst-case time Ω~(n2/S)\tildeΩ(n^2/S) per insertion is necessary for incremental algorithms, and sufficient for S≥nS\ge\sqrt{n}. (3) With amortization, incremental algorithms achieve O~(n/S)\tilde O(n/S) time per insertion with adjacency lists and O~(n2/S)\tilde O(n^2/S) with an adjacency matrix, while Ω~(n/S)\tildeΩ(\sqrt{n/S}) and Ω~(nn/S)\tildeΩ(n\sqrt{n/S}), respectively, are necessary. (4) Fully dynamic algorithms need amortized time Ω~(n/S)\tildeΩ(n/S) per update with adjacency lists and Ω~(n2/S)\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)Ω(n) words of space. In contrast, our lower bounds show that polynomial update time is necessary whenever S≤n1−εS\le n^{1-\varepsilon}, even for a single pair of vertices and even for incremental algorithms with amortized guarantees.

Paper details

vlnc:W_kf4ndu7q
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 13

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…