SETH-based Lower Bound for Dynamic Degeneracy

Abstract

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_{\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_{\max }$. 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:\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_{\max })\cdot n^k$ and amortized update time $f(d_{\max })\cdot n^{1-\delta }$.

arXiv comment20 pages, 4 figures