{"id":"arxiv/2610.40369","url":"https://arxiv.org/abs/2610.40369","tags":["cs.DS","cs.CC","cs.DM","math.CO"],"score":0,"title":"Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms","domain":"cs.DS","source":"arxiv","authors":["Abhishek Dhawan","Eren C. Kızıldağ","Neeladri Maitra","Cheng Mao","Timothy L. H. Wee"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{}}