Adaptive gap for Δ-degree graph reconstruction
Problem 5.3 (adaptive vs non-adaptive gap) · arXiv:2404.03472
Status open high confidence
Problem 5.3 asks whether a deterministic adaptive algorithm can reconstruct any graph of maximum degree $\Delta$ using $o(\Delta^3 \log(n/\Delta))$ MIS queries, potentially exploiting the gap with the adaptive lower bound of $\Omega(\Delta^2 \log(n/\Delta)/\log\Delta)$. The best known deterministic adaptive upper bound remains $O(\Delta^3 \log(n/\Delta))$ (using $O(\log\Delta)$ rounds of adaptivity), matching the non-adaptive case and established in Konrad–O'Sullivan–Traistaru (arXiv:2401.05845, ITCS 2025). No subsequent paper has closed the gap or shown a sub-cubic (in $\Delta$) deterministic adaptive algorithm.
Reviewer notes. The conjecture is closely related to Konrad, O'Sullivan, Traistaru (arXiv:2401.05845, ITCS 2025), which predates the source paper (v1 January 2024) and already established the $O(\Delta^3 \log(n/\Delta))$ deterministic adaptive bound (Corollary 2 of v4, December 2024). That paper does not reference Problem 5.3 explicitly. No follow-up was found in the indexed literature that beats this bound or proves adaptivity provably helps for deterministic algorithms. The randomised adaptive lower bound $\Omega(\Delta^2 \log(n/\Delta)/\log\Delta)$ from the source paper still leaves a factor-$\Delta\log\Delta$ gap with the upper bound, making this an appealing open problem.
Context
For adaptive algorithms the best lower bound drops to $\Omega(\Delta^{2}\log(n/\Delta)/\log\Delta)$ in both the deterministic and randomised settings, while the upper bounds match the non-adaptive case. This gap suggests adaptive algorithms might outperform non-adaptive ones, motivating the question of whether adaptivity yields a provable saving.
Notes. Parser assigned the label 'Problem 5.0' to all three problems in Section 5; this is likely Problem 5.3 or the third of several unnumbered problems.
Source paper
Lower bounds for graph reconstruction with maximal independent set queries
Lukas Michel, Alex Scott · 2024-04-04
https://arxiv.org/abs/2404.03472