{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreie4uiw6w6ybxlemwmgi55ko4e6fuevu73ojjmhlmbpgz4fka7ncr4",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3ml62vigv5ay2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.03893v1",
  "publishedAt": "2026-05-06T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "David Gamarnik",
    "Miklós Z. Rácz",
    "Gabe Schoenbach"
  ],
  "textContent": "**Authors:** David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach\n\nWe 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.",
  "title": "Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs"
}