Optimal Low-Degree Hardness of Maximum Independent Set

DOI10.4171/MSL/25MaRDI QIDQ6351212arXivFDO

Authors Alexander S. Wein

Publication date 13 October 2020

Published in arXiv

Full work available at URL https://doi.org/10.4171/MSL/25

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.CCcs.DSmath.PRstat.ML

Abstract: We study the algorithmic task of finding a large independent set in a sparse ErdH{o}s-R'{e}nyi random graph with $n$ vertices and average degree $d$. The maximum independent set is known to have size $(2logd/d)n$ in the double limit $noinfty$ followed by $doinfty$, but the best known polynomial-time algorithms can only find an independent set of half-optimal size $(logd/d)n$. We show that the class of low-degree polynomial algorithms can find independent sets of half-optimal size but no larger, improving upon a result of Gamarnik, Jagannath, and the author. This generalizes earlier work by Rahman and Vir'ag, which proved the analogous result for the weaker class of local algorithms.

This page was built for publication: Optimal Low-Degree Hardness of Maximum Independent Set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6351212)