Conditional limits on fast dynamic graph degeneracy approximation
SETH-based Lower Bound for Dynamic Degeneracy
Data Structures and Algorithms
Summary
Finding out how 'dense' different parts of a network are is important for understanding it. The authors look at how quickly this information can be updated as the network changes, by adding or removing connections. They show that it’s very unlikely we can build a tool that updates this information really fast and with high accuracy at the same time, unless a major assumption in computer science is wrong. Their work builds on previous methods that give a rough approximation but aren’t that fast or precise. This sets boundaries on what kinds of algorithms for tracking network density are possible.
What this means in practice
- •For graph algorithm designers: Avoid attempts to create very fast data structures with better than two-approximation for graph degeneracy updates under edge changes, based on this complexity lower bound.
- •For database engineers: Understand inherent trade-offs when maintaining approximate network density metrics in dynamic graph databases around insertions and deletions.
A theory result. No direct application yet.
Authors
Konrad Majewski, Michał Pilipczuk
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_{\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, δ> 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-δ}$.