Konrad Majewski

SETH-based Lower Bound for Dynamic Degeneracy

It is proved 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 and amortized update time.