Summary
Finding the largest set of edges in a network where no two edges share a vertex and are connected only to each other (an induced matching) is really hard in general. The authors show that in random networks, simple methods like greedy online algorithms can reliably find induced matchings that are about half the maximum possible size, and no online approach can do significantly better. They also prove that certain low-degree polynomial algorithms share this half-optimal limit. Their work uses new mathematical ideas to avoid complicated traditional proofs and shows that this half-size limit is a fundamental barrier for these algorithm types.
What this means in practice
- •For network algorithm designers: Design network algorithms knowing induced matching solutions cannot exceed half optimal size via online or low-degree methods in random graphs.
- •For online system developers: Set realistic expectations for online greedy algorithms finding induced matchings in dynamically revealed network data.
A theory result. No direct application yet.
Authors
Abhishek Dhawan, Eren C. Kızıldağ, Neeladri Maitra, Cheng Mao, Timothy L. H. Wee
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\le p\le 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(-Ω(L\log(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.