Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
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\H{o}s-R\'enyi random grap...