Papers for

online system developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Online and low-degree algorithms find half-size induced matchings in random graphs

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\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.

Thu 29 OctData Structures and AlgorithmsComputational ComplexityDiscrete Mathematics
The gist
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.
Open → 2610.40369v1