Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
Abstract
For many optimization problems on random graphs, most prominently the largest independent set problem, natural algorithms reach only half the optimum, and such factor-two gaps are known to be sharp within broad algorithmic classes. We prove such a gap for finding large induced matchings in Erdős-Rényi random graphs. In the worst case, requiring a matching to be induced turns a polynomial-time solvable problem into an NP-hard one; our results reveal an average-case counterpart. In G(n,p) with C/n≤ p≤ 1−κ, the largest induced matching has size (1+o(1))L with high probability, where L=log1/(1−p)(np). A simple online greedy algorithm finds an induced matching of size (1/2−ε)L, while no online algorithm, even with adaptive inspection order and unbounded computation, finds one of size (1/2+ε)L except with probability exp(−Ω(Llog(np))). In the sparse regime p=d/n, low-degree polynomial algorithms exhibit the same sharp threshold. Our guarantees rest on a maximality principle: with high probability, every maximal induced matching is half-optimal. Greedy outputs a maximal induced matching and our low-degree algorithm a near-maximal one. We bypass the delicate coupling arguments classically used to analyze greedy since Karp. For low-degree hardness, we adapt Wein's overlap gap argument, with forbidden structures that track overlaps between endpoint sets rather than edge sets, since a new edge may join two previously used endpoints and thus encounter no fresh randomness. For online hardness, we give a new and significantly simpler argument that avoids the correlated instances of prior OGP-based proofs: at a suitable stopping time, all pairs involving uninspected vertices remain unrevealed, so a direct first-moment bound suffices.
Related
- Graph Matching in Random Geometric Graphs I: Efficient Algorithms
- Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms
- Optimal path decompositions of sparse random graphs
- Optimal detection of geometry in random graphs and kernel matrices at critical thresholds
- Universality in random graphs via optimal linking systems: trees and beyond
BibTeX
@misc{dhawan2026halfoptimal,
title = {{Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms}},
author = {Abhishek Dhawan and Eren C. Kızıldağ and Neeladri Maitra and Cheng Mao and Timothy L. H. Wee},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40369},
eprint = {2610.40369},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40369},
}
RIS
TY - UNPB
TI - Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
AU - Abhishek Dhawan
AU - Eren C. Kızıldağ
AU - Neeladri Maitra
AU - Cheng Mao
AU - Timothy L. H. Wee
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40369
UR - https://arxiv.org/abs/2610.40369
AB - For many optimization problems on random graphs, most prominently the largest independent set problem, natural algorithms reach only half the optimum, and such factor-two gaps are known to be sharp within broad algorithmic classes. We prove such a gap for finding large induced matchings in Erdős-Rényi random graphs. In the worst case, requiring a matching to be induced turns a polynomial-time solvable problem into an NP-hard one; our results reveal an average-case counterpart. In G(n,p) with C/n≤ p≤ 1−κ, the largest induced matching has size (1+o(1))L with high probability, where L=log_1/(1−p)(np). A simple online greedy algorithm finds an induced matching of size (1/2−ε)L, while no online algorithm, even with adaptive inspection order and unbounded computation, finds one of size (1/2+ε)L except with probability exp(−Ω(Llog(np))). In the sparse regime p=d/n, low-degree polynomial algorithms exhibit the same sharp threshold. Our guarantees rest on a maximality principle: with high probability, every maximal induced matching is half-optimal. Greedy outputs a maximal induced matching and our low-degree algorithm a near-maximal one. We bypass the delicate coupling arguments classically used to analyze greedy since Karp. For low-degree hardness, we adapt Wein's overlap gap argument, with forbidden structures that track overlaps between endpoint sets rather than edge sets, since a new edge may join two previously used endpoints and thus encounter no fresh randomness. For online hardness, we give a new and significantly simpler argument that avoids the correlated instances of prior OGP-based proofs: at a suitable stopping time, all pairs involving uninspected vertices remain unrevealed, so a direct first-moment bound suffices.
ER -