Metraipolis › archive › dc_2e96f20286eb

Deterministic Connectivity Sketches Under Edge Deletions — arXiv:2611.06626

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.06626
License (as archived)
CC0-1.0
Archived
2026-11-05T18:31:41.363Z
SHA-256 of the archived text
7522b68080c253a9d7a4a72b4ed9044c528067da38fc5b08b195b565697cde86
Stable URL of this page
https://metraipolis.com/documento/dc_2e96f20286eb

How to cite

Deterministic Connectivity Sketches Under Edge Deletions — arXiv:2611.06626 — arXiv (en), https://arxiv.org/abs/2611.06626 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2e96f20286eb (Metraipolis archive dc_2e96f20286eb, sha256 7522b68080c253a9d7a4a72b4ed9044c528067da38fc5b08b195b565697cde86)
BibTeX
@misc{dc2e96f20286eb,
  title = {Deterministic Connectivity Sketches Under Edge Deletions — arXiv:2611.06626},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.06626},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2e96f20286eb; sha256 7522b68080c253a9d7a4a72b4ed9044c528067da38fc5b08b195b565697cde86},
  year = {2026}
}

Archived text

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

How much information about a graph is needed to determine its connectivity after arbitrary valid edge deletions? This question is at the heart of designing deterministic dynamic streaming algorithms for graph connectivity. Towards answering this question, we study the deterministic one-way communication problem in which Alice holds a graph $G_A = (V, E_A)$ on $n$ vertices, Bob holds a graph $G_B = (V, E_B)$ with $E_B \subseteq E_A$, and Alice sends a message $M \in \{0,1\}^m$ that allows Bob to decide whether $G_A - G_B$ is connected. Randomized sketches solve this problem using $\tilde O(n)$ bits, whereas deterministic recovery of even one surviving edge requires $\Omega(n^2)$ bits. We prove an upper bound of $m = \widetilde{O}(n^{7/4})$ bits and a lower bound of $m = \widetilde{\Omega}(n^{3/2})$ bits for deciding connectivity. Thus, connectivity admits a subquadratic deterministic representation despite the quadratic cost of edge recovery, but remains polynomially harder than its randomized counterpart. The upper bound immediately yields an $\widetilde{O}(n^{7/4})$-bit deterministic $n^2$-fault tolerant connectivity oracle, which reports the connected components of a graph $G$ after any valid set of edge deletions. We also obtain an $\tilde \Omega(n f^{1/4})$-bit lower bound for deterministic $f$-fault tolerant connectivity oracles for every $f \in [1,n^2]$. Finally, we show that the separation between connectivity and edge recovery persists in deterministic single-pass dynamic streams with bounded update multiplicity. For every fixed $\epsilon \in (0,1/3)$, our algorithm reports the connected components of the final simple graph using $\widetilde{O}(n^{15/8 + 3\epsilon/8})$ bits (subquadratic space), provided each edge undergoes at most $n^{\epsilon}$ insertion or deletion updates in total.

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.06626 — 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-05T18:21:04.030Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).