Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results using the Local Weak Convergence Method

David Gamarnik, Tomasz Nowicki, Grzegorz Swirscsz

Let $G(n,c/n)$ and $G_r(n)$ be an $n$-node sparse random graph and a sparse random $r$-regular graph, respectively, and let $\mathcal{I}(n,r)$ and $\mathcal{I}(n,c)$ be the sizes of the…