PaperlayerView exact revision on arXiv

Source-linked AI summary

SETH-based Lower Bound for Dynamic Degeneracy

Konrad Majewski, Michał Pilipczuk

arXiv:2609.16303v1cs.DS

TL;DR

The paper asks how efficiently a dynamic graph's degeneracy can be approximated after edge insertions and deletions. It reduces Orthogonal Vectors through Dynamic Circuit Evaluation to prove a conditional lower bound: unless SETH fails, approximation below factor 2 cannot have strongly sublinear amortized update time.

  • Problem

    The paper studies maintaining an approximate degeneracy value of a dynamic graph after edge insertions and deletions, with the reported value bounded by β·deg(G)+D.

    Source: §1 · p. 2

  • Method

    The proof reduces Orthogonal Vectors to Dynamic Circuit Evaluation and then reduces that problem to approximate degeneracy.

    Source: §1 · p. 3, §4 · p. 9

  • Results

    Unless SETH fails, no (2−ε)-approximation data structure achieves initialization time f(d_max)·n^k and amortized update time f(d_max)·n^(1−δ), for any ε, δ > 0, D, k, and f.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The result distinguishes dynamic degeneracy from arboricity, for which additive-error-2 approximation can be maintained efficiently.

    Source: §1 · p. 3

    The lower bound is conditional on SETH and uses the Orthogonal Vectors hardness statement for dimensions d ≤ O(n^δ).

    Source: §2 · pp. 4–5

Abstract

from arXiv · show

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}$.

1 Introduction

The paper studies dynamic degeneracy approximation and proves a SETH-based lower bound ruling out approximation factors below 2 with strongly sublinear amortized updates. Its proof reduces Orthogonal Vectors through Dynamic Circuit Evaluation, contrasting degeneracy with dynamic arboricity.

1 Introduction

  • Degeneracy and arboricity are within a factor of 2 and both measure uniform graph sparsity, but the theorem distinguishes their dynamic approximation complexities.The paper notes that degeneracy is prominent in structural graph theory, while dynamic and distributed algorithms often focus on arboricity.Source: §1 · pp. 2–3
  • The dynamic task starts from an edgeless n-vertex graph, permits edge insertions and deletions while deg(G) ≤ d_max, and requires an output d with deg(G) ≤ d ≤ β·deg(G)+D after each update.The paper studies maintaining an approximate degeneracy value under this update-and-query specification.Source: §1 · p. 2
  • Christiansen and Rotenberg give a worst-case poly(log n, d_max) update-time arboricity structure with additive error 2, which yields a (2, 3)-approximation for degeneracy.Given their arboricity estimate α, returning max(2α−1, 0) suffices.Source: §1 · p. 2
  • Unless SETH fails, Dynamic (2−ε, D)-Approximate Degeneracy admits no data structure with initialization time f(dmax)·n^k and amortized update time f(dmax)·n^(1−δ), for any ε, δ > 0, D, k∈N, and function f:N→N.Source: §1 · p. 3
  • A strongly sublinear-update structure for approximate degeneracy would solve Orthogonal Vectors in strongly subquadratic time, via Dynamic Circuit Evaluation.The reduction approach follows Abboud and Vassilevska Williams [1] and strengthens an approach of Pilipczuk, Siebertz, and Toruńczyk [5].Source: §1 · p. 3

2 Preliminaries

The preliminaries establish the graph, circuit, and fine-grained complexity notions used in the reductions. They state the SETH-based Orthogonal Vectors hardness and give a size-linear conversion to circuits with bounded input and output degrees.

2 Preliminaries

  • Degeneracy is the largest minimum degree among subgraphs, equivalently the least k for which every nonempty subgraph has a vertex of degree at most k.A k-degeneracy ordering exists exactly when deg(G) ≤ k, and an ordering removes each vertex with at most k later neighbors.Source: §2 · pp. 3–4
  • A Boolean circuit is an acyclic directed graph of gates and wires; monotone circuits use only AND and OR gates, while (2, 2)-circuits bound every gate's in-degree and out-degree by 2.Equivalent (2, 2)-circuits of size O(|C|) can be constructed while preserving monotonicity.Source: §2 · p. 4
  • SETH asserts that for every ε > 0, some k-SAT problem cannot be solved in O((2−ε)^n) time, and Orthogonal Vectors is the standard stepping stone to polynomial-time lower bounds.SETH was introduced by Impagliazzo and Paturi.Source: §2 · pp. 4–5
  • Unless SETH fails, Orthogonal Vectors in dimension d ≤ O(n^δ) cannot be solved in O(n^(2−ε)) time, for any ε, δ > 0.The preliminaries describe OV as asking whether two n-vector sets in {0,1}^d contain an orthogonal pair.Source: §2 · p. 5

3 From Orthogonal Vectors to Dynamic Circuit Evaluation

The section reduces Orthogonal Vectors to Dynamic Circuit Evaluation, establishing a SETH-based lower bound even for monotone (2,2)-circuits.

  • Dynamic Circuit Evaluation starts with a fixed circuit and input vector, flips one input bit per update, and reports the circuit output after each update.Source: §3 · p. 5
  • Unless SETH fails, Dynamic Circuit Evaluation has no data structure with initialization O(m^k) and amortized update O(m^(1−ε)), even for monotone (2,2)-circuits.Source: §3 · p. 6
  • OvToCircuit constructs a monotone (2,2)-circuit with O(nd) gates in O(nd) time, whose outputs detect orthogonal pairs across a sequence of inputs.The sequence can be chosen so each vector differs from the first in at most two positions; some output is zero exactly when an orthogonal pair exists.Source: §3 · p. 6
  • For each input xk, the constructed circuit outputs zero exactly when ak has an orthogonal partner in B.Switch inputs select ak; compare and orthogonal gates feed an AND output that is zero when some pair is orthogonal.Source: §3 · pp. 6–8
  • A hypothetical faster Dynamic Circuit Evaluation structure would make the Orthogonal Vectors algorithm run in strongly subquadratic time, contradicting its SETH-based hardness.Source: §3 · pp. 8–9
  • The reduction partitions A and B into equal-sized blocks, tests every block pair, and evaluates each input sequence using O(n′d) circuit updates.Successive inputs require at most four bit flips each after the first input is installed.Source: §3 · pp. 8–9

4 From Dynamic Circuit Evaluation to Dynamic Degeneracy

This section develops a dynamic reduction linking circuit evaluation and graph degeneracy, using a graph whose degeneracy ranges distinguish circuit outputs and whose updates reflect input flips. It uses this gap in a reduction involving dynamic degeneracy and monotone (2, 2)-circuit evaluation.

4 From Dynamic Circuit Evaluation to Dynamic Degeneracy

  • A linear-time O(m)-size circuit transformation makes every input have outdegree 1 and every OR gate have indegree 2 and outdegree 1, preserving evaluation and translating each input flip into O(1) flips.Both the transformed circuit and its initial input vector can be computed in O(m) time.Source: §4 · pp. 9–10
  • For fixed ℓ ≥ 2, CircuitToDegℓ initializes a graph with O(ℓ² · m) vertices and O(ℓ³ · m) edges in O(ℓ³ · m) time, and each input flip takes O(ℓ²) time.A flip is represented by O(ℓ²) edge updates.Source: §4 · p. 10
  • For inputs p with x(p)=0, losing edges to V out drops their degree to at most ℓ, triggering collapse of all remaining 0-valued gadgets and leaving G completely unraveled.Source: §4 · p. 11
  • The reduction generalizes an idea from [5, Appendix A] to every fixed ℓ, enabling an approximation gap arbitrarily close to 2.Source: §4 · p. 11

Graph size

  • The constructed graph has O(ℓ²m) vertices and O(ℓ³m) edges.The vertex bound sums the wire sets, OR- and AND-gadgets, and the output gadget; the edge bound follows from every vertex having degree less than 3ℓ.Source: §4 · p. 16

Initialization and updates

  • Initialization takes O(ℓ³m) time, and each modified input can be updated in O(ℓ²) time.Updates modify only the corresponding input gadget; the logic gates, wires, and output gadget remain static.Source: §4 · p. 17

Circuit evaluation vs degeneracy

  • When C(x) = 1, deg(G) ≤ ℓ; for C(x) = 0, the analysis constructs an induced subgraph with minimum degree at least 2ℓ−1.The construction also establishes the general upper bound deg(G) ≤ 3ℓ.Source: §4 · p. 17
  • The graph construction encodes the circuit output in disjoint degeneracy ranges: at most ℓ when C(x) = 1, and from 2ℓ−1 to 3ℓ when C(x) = 0.The constructed graph’s degeneracy remains at most dmax = 3ℓ.Source: §4 · p. 18
  • Comparing the maintained degeneracy estimate with 2ℓ−1 lets the reduction determine C(x) in O(1) time after initialization and each update.The circuit value 0 implies degeneracy at least 2ℓ−1, whereas value 1 implies degeneracy at most ℓ.Source: §4 · pp. 18–19
  • The assumed degeneracy structure would yield circuit evaluation with initialization O(m^k') and amortized update O(m^(1−δ)), contradicting Lemma 3.1.Here k' = max(k, 2), and m is the circuit size.Source: §4 · pp. 18–20

AI disclosure

The authors used Gemini 3.6 Flash for language and style refinement, proof verification assistance, and LaTeX code for Figs. 1 to 4. They state that the authors developed the theoretical concepts and core proofs and reviewed, checked, and edited all outputs.

  • Gemini 3.6 Flash assisted with language and style refinement, proof verification, and LaTeX code for Figs. 1 to 4.Source: AI disclosure · p. 20
  • The authors state that they developed the theoretical concepts and core proofs.Source: AI disclosure · p. 20
  • The authors reviewed, checked, and edited all outputs and take full responsibility for the paper’s contents.Source: AI disclosure · p. 20
Loading 2609.16303v1…