Metraipolis › archive › dc_6c7732b59487

SETH-based Lower Bound for Dynamic Degeneracy — arXiv:2609.16303

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.16303
License (as archived)
CC0-1.0
Archived
2026-10-15T21:59:07.319Z
SHA-256 of the archived text
029ca902cb05ea52cb34deff6b69fb70b4beb8cffe2ae00879f211f5702f2328
Stable URL of this page
https://metraipolis.com/documento/dc_6c7732b59487

How to cite

SETH-based Lower Bound for Dynamic Degeneracy — arXiv:2609.16303 — arXiv (en), https://arxiv.org/abs/2609.16303 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6c7732b59487 (Metraipolis archive dc_6c7732b59487, sha256 029ca902cb05ea52cb34deff6b69fb70b4beb8cffe2ae00879f211f5702f2328)
BibTeX
@misc{dc6c7732b59487,
  title = {SETH-based Lower Bound for Dynamic Degeneracy — arXiv:2609.16303},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.16303},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6c7732b59487; sha256 029ca902cb05ea52cb34deff6b69fb70b4beb8cffe2ae00879f211f5702f2328},
  year = {2026}
}

Archived text

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

In this work, we consider the problem of maintaining an approximate value of degeneracy of a given dynamic $n$-vertex graph $G$ updated by edge insertions and deletions. From the work of Christiansen and Rotenberg [ICALP 2022], it follows that one can design a dynamic data structure for this problem with worst-case update time $\text{poly}(d_{\mathrm{max}}, \log n)$ that maintains an integer between $d$ and $2d+3$ where $d$ is the degeneracy of $G$, under the assumption that $d$ never exceeds $d_{\mathrm{max}}$. We complement their result by providing a conditional lower bound: we prove that, unless SETH fails, for any $\varepsilon, \delta > 0$, $k \in \mathbb{N}$, and function $f\colon \mathbb{N}\to \mathbb{N}$, there is no data structure which maintains a $(2-\varepsilon)$-approximation of the degeneracy of $G$ with initialization time $f(d_{\mathrm{max}})\cdot n^k$ and amortized update time $f(d_{\mathrm{max}})\cdot n^{1-\delta}$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-16 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.16303 — 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-10-15T21:46:54.564Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).