Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems

We establish the first update-time separation between dynamic algorithms against oblivious adversaries and those against adaptive adversaries in natural dynamic graph problems, based on popular fine-grained complexity hypotheses.

Specifically, under the combinatorial BMM hypothesis, we show that every combinatorial algorithm against an adaptive adversary for the incremental maximal independent set problem requires n 1-o(1) amortized update time. Furthermore, assuming either the 3SUM or APSP hypotheses, every algorithm for the decremental maximal clique problem needs ∆/n o(1) amortized update time when the initial maximum degree is ∆ ≤ √ n. These lower bounds are matched by existing algorithms against adaptive adversaries. In contrast, both problems admit algorithms against oblivious adversaries that achieve polylog(n) amortized update time [BDH + 19, CZ19]. Therefore, our separations are exponential.

Previously known separations for dynamic algorithms were either engineered for contrived problems and relied on strong cryptographic assumptions [BKM + 22], or worked for problems whose inputs are not explicitly given but are accessed through oracle calls [BEF + 23].

As a byproduct, we also provide a separation between incremental and decremental algorithms for the triangle detection problem: we show a decremental algorithm with Õ(n ω ) total update time, while every incremental algorithm requires n 3-o(1) total update time, assuming the OMv hypothesis. To our knowledge this is the first separation of this kind.