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 n1-o(1) amortized update time. Furthermore, assuming either the 3SUM or APSP hypotheses, every algorithm for the decremental maximal clique problem needs Delta/no(1) amortized update time when the initial maximum degree is Delta ≤ √n. These lower bounds are matched by existing algorithms against adaptive adversaries. In contrast, both problems admit algorithms against oblivious adversaries that achieve operatornamepolylog(n) amortized update time [Behnezhad, Derakhshan, Hajiaghayi, Stein, Sudan; FOCS '19] [Chechik, Zhang; FOCS '19]. Therefore, our separations are exponential. Previously known separations for dynamic algorithms were either engineered for contrived problems and relied on strong cryptographic assumptions [Beimel, Kaplan, Mansour, Nissim, Saranurak, Stemmer; STOC '22], or worked for problems whose inputs are not explicitly given but are accessed through oracle calls [Bateni, Esfandiari, Fichtenberger, Henzinger, Jayaram, Mirrokni, Wiese; SODA '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 tildeO(nω) total update time, while every incremental algorithm requires n3-o(1) total update time, assuming the OMv hypothesis. To our knowledge this is the first separation of this kind.