Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
For researchers in combinatorial optimization and online algorithms, this work provides tight hardness results for online algorithms on a fundamental graph problem, revealing a gap between online and offline performance.
The paper studies the problem of finding large common induced subgraphs in two independent Erdős–Rényi random graphs. It shows that a simple greedy online algorithm achieves a common induced subgraph of size (2-o(1)) log₂ n, and proves that no online algorithm can achieve size (2+ε) log₂ n, establishing a computation-to-optimization gap.
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 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, Kizildağ, and Warnke that connects OGP and online algorithms.