Metraipolis › archive › dc_9deadfe4ebf4

Connectivity in a New Bounded-Space Dynamic Model — arXiv:2611.08351

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.08351
License (as archived): CC0-1.0
Archived: 2026-11-06T14:54:26.859Z
SHA-256 of the archived text: 19d118d692737e583fc085323a4bcc49ec4e0c3763abcdea7891b5cf40650f6d
Stable URL of this page: https://metraipolis.com/documento/dc_9deadfe4ebf4

How to cite

Connectivity in a New Bounded-Space Dynamic Model — arXiv:2611.08351 — arXiv (en), https://arxiv.org/abs/2611.08351 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9deadfe4ebf4 (Metraipolis archive dc_9deadfe4ebf4, sha256 19d118d692737e583fc085323a4bcc49ec4e0c3763abcdea7891b5cf40650f6d)

BibTeX

@misc{dc9deadfe4ebf4,
  title = {Connectivity in a New Bounded-Space Dynamic Model — arXiv:2611.08351},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.08351},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9deadfe4ebf4; sha256 19d118d692737e583fc085323a4bcc49ec4e0c3763abcdea7891b5cf40650f6d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.08351. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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\Theta(n^2/S^2)$ per insertion is necessary and sufficient for incremental algorithms. (2) With an adjacency matrix, worst-case time $\tilde\Omega(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\Omega(\sqrt{n/S})$ and $\tilde\Omega(n\sqrt{n/S})$, respectively, are necessary. (4) Fully dynamic algorithms need amortized time $\tilde\Omega(n/S)$ per update with adjacency lists and $\tilde\Omega(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 $\Omega(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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.08351 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:26:57.633Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).