arxiv: 2605.03893 · v1 · submitted 2026-05-05 · 💻 cs.DS · cs.CC· cs.DM· math.CO· math.PR

Recognition: unknown

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs

David Gamarnik , Mikl\'os Z. R\'acz , Gabe Schoenbach

Authors on Pith no claims yet

Pith reviewed 2026-05-07 13:41 UTC · model grok-4.3

classification 💻 cs.DS cs.CCcs.DMmath.COmath.PR

keywords common induced subgraphsErdős–Rényi graphsonline algorithmsoverlap gap propertyrandom graphscomputation-optimization gapinterpolation argument

0 comments

The pith

No online algorithm can find a common induced subgraph of size (2+ε)log₂n in two random graphs with probability bounded away from zero.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the problem of recovering large common induced subgraphs between two independent Erdős–Rényi random graphs G1 and G2 on n vertices. The optimum size is known to be (4-o(1))log₂n with high probability. A simple greedy online procedure already reaches (2-o(1))log₂n, yet the main theorem shows that no online algorithm can reach (2+ε)log₂n with probability that remains positive as n grows. This separation supplies concrete evidence of a computation-to-optimization gap. The proof proceeds by establishing that the set of large common induced subgraphs satisfies a multi-overlap gap property and then invoking an interpolation argument that turns the gap into an online lower bound.

Core claim

In two independent random graphs G1 and G2, the largest common induced subgraph has size (4-o(1))log₂n, but no online algorithm can output one of size (2+ε)log₂n with probability that stays positive as n grows. The authors establish this by proving that the set of large common induced subgraphs satisfies the multi-overlap gap property, which an interpolation method then converts into an impossibility result for online algorithms.

What carries the argument

The multi-overlap gap property of the solution space of large common induced subgraphs, which prevents online algorithms from reaching beyond the (2+o(1))log₂n threshold via an interpolation argument.

If this is right

A simple greedy online algorithm already achieves size (2-o(1))log₂n with high probability.
The existence of the multi-overlap gap property implies a strict separation between the optimum and what any online procedure can achieve.
The same interpolation technique can be applied to derive online hardness for other random optimization problems that possess an overlap gap.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the multi-overlap gap property holds for other subgraph recovery tasks, online algorithms will be similarly limited even when the true optimum is larger.
Algorithms allowed a small amount of offline preprocessing or limited lookahead might cross the 2 log₂n barrier and reach sizes closer to the optimum.
Direct numerical checks of the overlap gap on moderate-sized instances could test whether the property persists beyond the asymptotic regime.

Load-bearing premise

The solution space of large common induced subgraphs exhibits the multi-overlap gap property.

What would settle it

An explicit online algorithm that, for arbitrarily large n, outputs a common induced subgraph of size at least (2.1)log₂n with probability at least 0.01 would falsify the main impossibility theorem.

Figures

Figures reproduced from arXiv: 2605.03893 by David Gamarnik, Gabe Schoenbach, Mikl\'os Z. R\'acz.

**Figure 1.** Figure 1: A family of interpolation paths based on view at source ↗

**Figure 2.** Figure 2: Xm,t counts the number of sets of large solutions {σi}i∈[m] to the LCIS(n) problem with a particular overlap pattern; we visualize one such set here. Each σi := (Hi,1, Hi,2) is a pair of isomorphic subgraphs of Y (t) i = G (t) i,1 , G(t) i,2 , with |σi | ≥ (2 + ε)log2 n. To see the overlap pattern, we overlay each V (Hi,j ) onto nj := [n], where the vertices P (t) j processed by A through step t are co… view at source ↗

read the original abstract

We study the problem of efficiently finding large common induced subgraphs of two independent Erd\H{o}s--R\'enyi 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\u{g}, and Warnke that connects OGP and online algorithms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves no online algorithm beats (2+ε)log₂n for common induced subgraphs in two random graphs, matching their own greedy construction while the offline optimum sits at (4-o(1))log₂n.

read the letter

The main point is that online algorithms cannot find a common induced subgraph of size (2+ε)log₂n with probability bounded away from zero, while a basic greedy online method already reaches (2-o(1))log₂n. This sits between the information-theoretic optimum of (4-o(1))log₂n and what online methods can achieve, giving a concrete gap for this problem. The new piece is the application of the multi-overlap gap property plus the Gamarnik-Kizildağ-Warnke interpolation to turn that property into an online lower bound; earlier work stopped at the offline size. They also supply the matching greedy upper bound, which makes the online result feel tight rather than loose. The argument stays consistent with prior OGP results and does not introduce fitted parameters or circular definitions. The only real soft spot is that the OGP verification for this specific solution space is the load-bearing step, and any small error there would affect how sharp the (2+ε) threshold is, though the overall direction and the matching upper bound make the claim believable. This is useful for researchers who care about online versus offline gaps in random-graph optimization or who want templates for applying interpolation arguments to new problems. It is worth sending to peer review because the result is self-contained, the tools are established, and the gap it identifies is natural.

Referee Report

1 major / 3 minor

Summary. The paper studies the online problem of finding large common induced subgraphs between two independent Erdős–Rényi graphs G₁, G₂ ∼ G(n, 1/2). It first shows that a simple greedy online algorithm finds a common induced subgraph of size (2−o(1)) log₂ n with high probability. The main result proves that no online algorithm can find one of size at least (2+ε) log₂ n with probability bounded away from zero as n→∞. The impossibility is obtained by establishing a multi-overlap gap property for the space of large common induced subgraphs and invoking the Gamarnik–Kizildağ–Warnke interpolation argument. This is contrasted with the offline optimum of (4−o(1)) log₂ n shown by Chatterjee and Diaconis.

Significance. If the central claims hold, the work is significant because it supplies matching (2−o(1)) upper and lower bounds for online algorithms, thereby giving concrete evidence of a computation-to-optimization gap for this random-graph problem. A strength is the direct application of the multi-OGP plus interpolation technique to a new combinatorial setting without introducing fitted parameters or self-referential reductions; the argument is internally consistent with the known offline threshold.

major comments (1)

[§4] §4, Theorem 4.2 (multi-OGP statement): the overlap threshold τ is chosen so that the probability of two solutions having overlap in (τ,1−τ) is exponentially small; an explicit second-moment calculation or reference to the precise constant that makes the interpolation apply without additional error terms would strengthen the load-bearing step.

minor comments (3)

[Abstract] Abstract and §1: the phrase “with probability bounded away from 0” should be stated uniformly as “with probability ≥ δ > 0 for some δ independent of n”.
[§3] §3 (greedy algorithm): the analysis of the (2−o(1)) guarantee would benefit from a short pseudocode block and an explicit statement of the high-probability event used in the concentration argument.
[§5] §5 (interpolation): the invocation of Gamarnik–Kizildağ–Warnke is clear at high level, but a one-sentence reminder of the precise hypotheses (e.g., the required tail bounds on the overlap distribution) would help readers verify applicability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment of significance, and recommendation for minor revision. We address the single major comment below and will incorporate the suggested strengthening in the revised manuscript.

read point-by-point responses

Referee: [§4] §4, Theorem 4.2 (multi-OGP statement): the overlap threshold τ is chosen so that the probability of two solutions having overlap in (τ,1−τ) is exponentially small; an explicit second-moment calculation or reference to the precise constant that makes the interpolation apply without additional error terms would strengthen the load-bearing step.

Authors: We agree that an explicit second-moment calculation would improve clarity and self-containment. In the revised version we will expand the proof of Theorem 4.2 to include a direct second-moment computation (following the same moment-method approach used for the offline threshold in Chatterjee-Diaconis) that identifies the precise constant τ (approximately 0.25 in this balanced random-graph setting) for which the probability of overlap in (τ,1−τ) is at most exp(−Ω(n)). This bound is strong enough to invoke the Gamarnik-Kizildağ-Warnke interpolation directly, with no additional error terms, and we will state the resulting constant explicitly. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via new OGP proof

full rationale

The paper establishes the multi-overlap gap property directly for the common induced subgraph problem on two independent G(n,1/2) graphs and then invokes a general interpolation theorem from prior literature to convert OGP into an online-algorithm lower bound. The OGP proof is original to this manuscript and does not reduce to any self-referential definition, fitted parameter, or renaming of a known result. Although the cited interpolation work shares an author, it functions as an external general tool applied to a new instance rather than a load-bearing premise justified solely by self-citation; the central claim therefore remains independent of any circular reduction within the present paper.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the overlap gap property holding for the solution space and on the interpolation argument correctly translating that property into an online lower bound; both are domain assumptions imported from prior literature rather than derived inside the paper.

axioms (2)

domain assumption The solution space of large common induced subgraphs in two independent G(n,1/2) graphs exhibits the (multi) overlap gap property.
Invoked as the structural property that the interpolation argument converts into online hardness.
domain assumption The interpolation argument developed by Gamarnik, Kizildag, and Warnke connects the overlap gap property to limitations on online algorithms.
Cited directly as the bridge from OGP to the impossibility statement.

pith-pipeline@v0.9.0 · 5558 in / 1510 out tokens · 75992 ms · 2026-05-07T13:41:45.005609+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

27 extracted references · 1 canonical work pages

[1]

Probability Theory and Related Fields , pages=

The algorithmic phase transition of random graph alignment problem , author=. Probability Theory and Related Fields , pages=. 2025 , publisher=

2025
[2]

The Thirty Sixth Annual Conference on Learning Theory (COLT) , pages=

Gamarnik, David and Kizilda. The Thirty Sixth Annual Conference on Learning Theory (COLT) , pages=. 2023 , organization=

2023
[3]

2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages=

Gamarnik, David and K. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2022 , organization=

2022
[4]

Huang, Brice and Sellke, Mark , year=
[5]

Sharp bounds for online algorithms , author=

Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms , author=. Electronic Communications in Probability , volume=. 2026 , publisher=

2026
[6]

The Annals of Probability , number =

David Gamarnik and Madhu Sudan , title =. The Annals of Probability , number =
[7]

The Annals of Probability , number =

Mustazee Rahman and B. The Annals of Probability , number =
[8]

, title =

Gamarnik, David and Jagannath, Aukosh and Wein, Alexander S. , title =. SIAM Journal on Computing , volume =
[9]

Proceedings of the National Academy of Sciences , volume =

David Gamarnik , title =. Proceedings of the National Academy of Sciences , volume =. 2021 , abstract =

2021
[10]

David Gamarnik , journal=
[11]

2025 , eprint=

Some easy optimization problems have the overlap-gap property , author=. 2025 , eprint=

2025
[12]

2025 , isbn =

Vafa, Neekon and Vaikuntanathan, Vinod , title =. 2025 , isbn =. doi:10.1145/3717823.3718263 , booktitle =

work page doi:10.1145/3717823.3718263 2025
[13]

2022 , eprint=

Isomorphisms between random graphs , author=. 2022 , eprint=

2022
[14]

Journal of Combinatorial Theory, Series B , volume=

Isomorphisms between random graphs , author=. Journal of Combinatorial Theory, Series B , volume=. 2023 , publisher=

2023
[15]

Combinatorica , volume =

Isomorphisms Between Dense Random Graphs , author =. Combinatorica , volume =
[16]

2025 , note=

A combinatorial approach to phase transitions in random graph isomorphism problems , author=. 2025 , note=

2025
[17]

, title =

Wein, Alexander S. , title =. Mathematical Statistics and Learning , volume =
[18]

2022 , eprint=

Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses , author=. 2022 , eprint=

2022
[19]

2025 , publisher=

Huang, Brice and Sellke, Mark , journal=. 2025 , publisher=

2025
[20]

Finding a large submatrix of a Gaussian random matrix , author=
[21]

2025 , note=

Optimal Hardness of Online Algorithms for Large Independent Sets , author=. 2025 , note=

2025
[22]

, Title=

Karp, Richard M. , Title=. 1976 , Month=

1976
[23]

International Journal of Pattern Recognition and Artificial Intelligence , volume=

Thirty years of graph matching in pattern recognition , author=. International Journal of Pattern Recognition and Artificial Intelligence , volume=. 2004 , publisher=

2004
[24]

Wiley Interdisciplinary Reviews (WIREs): Computational Molecular Science , volume=

Maximum common subgraph isomorphism algorithms and their applications in molecular science: a review , author=. Wiley Interdisciplinary Reviews (WIREs): Computational Molecular Science , volume=. 2011 , publisher=

2011
[25]

Annals of Mathematics and Artificial Intelligence , volume=

A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics , author=. Annals of Mathematics and Artificial Intelligence , volume=. 2013 , publisher=

2013
[26]

Annual Symposium on Theoretical Aspects of Computer Science (STACS) , pages=

On the approximability of the maximum common subgraph problem , author=. Annual Symposium on Theoretical Aspects of Computer Science (STACS) , pages=. 1992 , organization=

1992
[27]

Mathematical Proceedings of the Cambridge Philosophical Society , volume=

On colouring random graphs , author=. Mathematical Proceedings of the Cambridge Philosophical Society , volume=. 1975 , organization=

1975