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 - connectivity: after every edge update to an -vertex graph, an algorithm with words of workspace must report whether and are connected. The graph is accessed via adjacency list queries (degree, -th neighbor) or adjacency matrix queries. Our algorithms are randomized; our lower bounds hold for randomized algorithms with bits of workspace, a small constant ( for the worst-case matrix bound). We prove: (1) With adjacency lists, worst-case time per insertion is necessary and sufficient for incremental algorithms. (2) With an adjacency matrix, worst-case time per insertion is necessary for incremental algorithms, and sufficient for . (3) With amortization, incremental algorithms achieve time per insertion with adjacency lists and with an adjacency matrix, while and , respectively, are necessary. (4) Fully dynamic algorithms need amortized time per update with adjacency lists and with an adjacency matrix, even on forests, where both bounds are tight (lists: under bounded degree). Conventional dynamic connectivity admits polylogarithmic update time with words of space. In contrast, our lower bounds show that polynomial update time is necessary whenever , even for a single pair of vertices and even for incremental algorithms with amortized guarantees.