SETH-based Lower Bound for Dynamic Degeneracy

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{m}\mathrm{a}\mathrm{x}},\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{m}\mathrm{a}\mathrm{x}}$. We complement their result by providing a conditional lower bound: we prove that, unless SETH fails, for any $\epsilon ,\delta >0$, $k\in \mathbb{N}$, and function $f\text{\hspace{0.17em}⁣}:\mathbb{N}\to \mathbb{N}$, there is no data structure which maintains a $(2-\epsilon )$-approximation of the degeneracy of $G$ with initialization time $f(d_{\mathrm{m}\mathrm{a}\mathrm{x}})\cdot n^k$ and amortized update time $f(d_{\mathrm{m}\mathrm{a}\mathrm{x}})\cdot n^{1-\delta }$.