Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs

David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2537-2560, 2026.

Abstract

We study the problem of efficiently finding large common induced subgraphs of two independent Erdős–Rényi random graphs $G_1, G_2 \sim \mathbb{G}(n,1/2)$. Recently, Chatterjee and Diaconis (2023) showed that the largest common induced subgraph of $G_1$ and $G_2$ has size $(4-o(1))\log_2 n$ with high probability. We first show that a simple greedy online algorithm finds a common induced subgraph of $G_1$ and $G_2$ of size $(2-o(1)) \log_2 n$ with high probability. Our main result shows that no online algorithm can find a common induced subgraph of $G_1$ and $G_2$ of size at least $(2+\varepsilon) \log_2 n$ with probability bounded away from $0$ as $n \to \infty$. Together, these results provide evidence that this problem exhibits a computation-to-optimization gap. To prove the impossibility result, we show that the solution space of the problem exhibits a version of the (multi) overlap gap property (OGP), and utilize an interpolation argument recently developed by Gamarnik, K{ı}z{ı}ldağ, and Warnke (2025) that connects OGP and online algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-gamarnik26a, title = {Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs}, author = {Gamarnik, David and R{\'a}cz, Mikl{\'o}s Z. and Schoenbach, Gabe}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {2537--2560}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/gamarnik26a/gamarnik26a.pdf}, url = {https://proceedings.mlr.press/v336/gamarnik26a.html}, abstract = { We study the problem of efficiently finding large common induced subgraphs of two independent Erdős–Rényi random graphs $G_1, G_2 \sim \mathbb{G}(n,1/2)$. Recently, Chatterjee and Diaconis (2023) showed that the largest common induced subgraph of $G_1$ and $G_2$ has size $(4-o(1))\log_2 n$ with high probability. We first show that a simple greedy online algorithm finds a common induced subgraph of $G_1$ and $G_2$ of size $(2-o(1)) \log_2 n$ with high probability. Our main result shows that no online algorithm can find a common induced subgraph of $G_1$ and $G_2$ of size at least $(2+\varepsilon) \log_2 n$ with probability bounded away from $0$ as $n \to \infty$. Together, these results provide evidence that this problem exhibits a computation-to-optimization gap. To prove the impossibility result, we show that the solution space of the problem exhibits a version of the (multi) overlap gap property (OGP), and utilize an interpolation argument recently developed by Gamarnik, K{ı}z{ı}ldağ, and Warnke (2025) that connects OGP and online algorithms. } }
Endnote
%0 Conference Paper %T Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs %A David Gamarnik %A Miklós Z. Rácz %A Gabe Schoenbach %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-gamarnik26a %I PMLR %P 2537--2560 %U https://proceedings.mlr.press/v336/gamarnik26a.html %V 336 %X We study the problem of efficiently finding large common induced subgraphs of two independent Erdős–Rényi random graphs $G_1, G_2 \sim \mathbb{G}(n,1/2)$. Recently, Chatterjee and Diaconis (2023) showed that the largest common induced subgraph of $G_1$ and $G_2$ has size $(4-o(1))\log_2 n$ with high probability. We first show that a simple greedy online algorithm finds a common induced subgraph of $G_1$ and $G_2$ of size $(2-o(1)) \log_2 n$ with high probability. Our main result shows that no online algorithm can find a common induced subgraph of $G_1$ and $G_2$ of size at least $(2+\varepsilon) \log_2 n$ with probability bounded away from $0$ as $n \to \infty$. Together, these results provide evidence that this problem exhibits a computation-to-optimization gap. To prove the impossibility result, we show that the solution space of the problem exhibits a version of the (multi) overlap gap property (OGP), and utilize an interpolation argument recently developed by Gamarnik, K{ı}z{ı}ldağ, and Warnke (2025) that connects OGP and online algorithms.
APA
Gamarnik, D., Rácz, M.Z. & Schoenbach, G.. (2026). Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:2537-2560 Available from https://proceedings.mlr.press/v336/gamarnik26a.html.

Related Material