Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs

摘要

We study the problem of efficiently finding large common induced subgraphs of two independent Erdős–Rényi random graphs G_1, G_2 ∼𝔾(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+ε) log_2 n with probability bounded away from 0 as n →∞. 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.