Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach · 2026
Read Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs by David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03893.txt.
Introduction
David Gamarnik, Miklós Z. Rácz, and Gabe Schoenbach study the problem of finding large common induced subgraphs of two independent random graphs. Chatterjee and Diaconis recently showed the largest such shared structure has size about four times the base-two logarithm of the number of vertices. The question here is what online algorithms, which must commit to vertices as they arrive, can achieve.
A simple greedy online algorithm reaches about half the optimal size, two times the logarithm. The main result proves no online algorithm can do better: none finds a common induced subgraph of size above that threshold with probability bounded away from zero. The proof uses a version of the overlap gap property plus an interpolation argument, suggesting a genuine computation-to-optimization gap.
Catalog record
| CREATOR | David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.03893
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach 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 ∼ 𝔾 ( n , 1 / 2 ) G_{1},G_{2}\sim\mathbb{G}(n,1/2) . Recently, Chatterjee and Diaconis [ 2 ] showed that the largest common induced subgraph of G 1 G_{1} and G 2 G_{2} has size ( 4 − o ( 1 ) ) log 2 n (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 G_{1} and G 2 G_{2} of size ( 2 − o ( 1 ) ) log 2 n (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 G_{1} and G 2 G_{2} of size at least ( 2 + ε ) log 2 n (2+\varepsilon)\log_{2}n with probability bounded away from 0 0 as n → ∞ 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 [ 10 ] that connects OGP and online algorithms. 1 Introduction In the largest common induced subgraph ( \mathsf{LCIS} ) problem, the input is a pair of graphs G_{1} and G_{2} , and the goal is to find a common induced subgraph of G_{1} and G_{2} with as many vertices as possible. A solution \sigma=(H_{1},H_{2}) is any pair of induced subgraphs H_{1}\subseteq G_{1} and H_{2}\subseteq G_{2} such that H_{1}\cong H_{2} , where \cong denotes graph isomorphism. The size of the solution |\sigma|:=|H_{1}|=|H_{2}| is the number of vertices of the common subgraph and the goal is to maximize this quantity. The \mathsf{LCIS} problem is a fundamental optimization problem with close connections to other central problems such as graph isomorphism and graph matching, and it arises naturally in many applications, such as bioinformatics [ 6 ] , chemoinformatics [ 20 ] , and pattern recognition [ 3 ] . It is computationally hard in the worst case, even to approximate within any reasonable factor [ 17 ] . In this paper we study arguably the simplest and most natural average-case version of the \mathsf{LCIS} problem, where G_{1},G_{2}\sim\mathbb{G}(n,1/2) are independent Erdős–Rényi random graphs with n vertices and edge probability 1/2 ; we refer to this problem as \mathsf{LCIS}(n) . Recently, Chatterjee and Diaconis [ 2 ] showed that the largest solution has size (4-o(1))\log_{2}n with high probability as n\to\infty . 1 1 1 In fact, they proved a much more precise two-point concentration result; however, in this paper we primarily focus on the leading order term. , 2 2 2 Throughout the paper, we say that an event holds with high probability if its probability tends to 1 as n\to\infty . In this work, we initiate the study of the algorithmic side of the \mathsf{LCIS}(n) problem. We ask: What are the limits of efficient algorithms that solve \mathsf{LCIS}(n) with high probability? In particular, we focus on a broad class of online algorithms, which arise naturally for this problem. We first show that a simple greedy online algorithm finds a solution of size at least (2-o(1))\log_{2}n with high probability. In other words, this efficient algorithm is half-optimal and serves as a natural benchmark. Theorem 1 (Algorithms, informal) . There exists an efficient online algorithm that finds a solution to \mathsf{LCIS}(n) that has size at least (2-o(1))\log_{2}n with high probability as n\to\infty . Our main result shows that no online algorithm can do better than half-optimal. The class of online algorithms we consider is broad; roughly, it is defined as follows. An online algorithm for \mathsf{LCIS} processes the two graphs G_{1} and G_{2} one vertex pair (u_{t},v_{t})\in V(G_{1})\times V(G_{2}) at a time. When a vertex pair is processed, all connections of u_{t} and v_{t} to previously processed vertices are revealed (in G_{1} and G_{2} , respectively). The algorithm then has to make a decision whether or not to add a pair of vertices to the partial solution it has built so far. The main constraints are that both of the added vertices must have been already processed and at least one of them must be u_{t} or v_{t} . Notably, an online algorithm does not have to add both u_{t} and v_{t} at the same time, and as a result, it is possible for an individual vertex to be added to the solution well after it was originally processed. This is a fundamental difference compared to online algorithms for problems involving a single graph, where usually an immediate decision must be made about a vertex as soon as it is processed. 3 3 3 We note that in the problem of finding large cliques in the “one-dimensional” single graph case considered earlier in [ 10 ] , postponing the decision about including/excluding u_{t} trivializes the problem. Indeed, one can delay all decisions until all but (2-o(1))\log_{2}n vertices are revealed, find a nearly largest clique among the revealed vertices, and then include the vertices of the discovered clique in the last (2-o(1))\log_{2}n rounds. This difference stems from the “two-dimensional” nature of the \mathsf{LCIS} problem, with the input being two graphs. We defer formal definitions to Section 1.2 below. Theorem 2 (Impossibility, informal) . Fix any \varepsilon>0 . There is no online algorithm for \mathsf{LCIS}(n) that finds a solution of size at least (2+\varepsilon)\log_{2}n with probability bounded away from 0 as n\to\infty . Overall, these results combined provide evidence that the \mathsf{LCIS}(n) problem exhibits a computation-to-optimization gap. We next turn to describing our results more formally and in more detail. 1.1 A half-optimal greedy online algorithm A naive brute-force approach to finding a size- k solution to \mathsf{LCIS}(n) would require checking all pairs of size- k subgraphs of G_{1} and G_{2} . For k=\Theta(\log n) , such an exhaustive approach would require superpolynomial runtime, since \binom{n}{k}^{2}\geq(n/k)^{2k}\geq n^{\Omega(\log n)} . To get a polynomial-time algorithm, a useful initial observation is that independent sets of equal size are isomorphic, so any algorithm that finds independent sets can also solve the \mathsf{LCIS} problem (and the same applies to cliques). The largest independent set in G\sim\mathbb{G}(n,1/2) has size (2-o(1))\log_{2}n with high probability and a simple greedy online algorithm finds an independent set of size (1+o(1))\log_{2}n [ 14 , 18 ] . So this immediately gives an efficient quarter-optimal solution to \mathsf{LCIS}(n) : use a greedy algorithm to find independent sets of size (1+o(1))\log_{2}n in both G_{1} and G_{2} . However, there is no known efficient algorithm to find an independent set of size (1+\varepsilon)\log_{2}n in G\sim\mathbb{G}(n,1/2) — indeed, it is conjectured that such an algorithm does not exist — so it is not immediately clear how to go beyond this. The key idea is to tailor the greedy algorithm for finding an independent set to the \mathsf{LCIS} problem. Recall first the algorithm for finding an independent set in a single graph G [ 14 , 18 ]