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

Let $G(n,c\mathrm{/}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 ${\cal I}(n,c)$bethesizesofthelargestindependentsetin$G(n,c/n)$and$G_r(n)$\mathrm{.}Theasymptoticvalueof${\cal I}(n,c)/n$as$n\to\infty$, can be computed using the Karp-Sipser algorithm when $c\le e$. For random cubic graphs, $r=3$, it is only known that $.432\leq\liminf_n {\cal I}(n,3)/n \leq \limsup_n {\cal I}(n,3)\leq .4591$withhighprobability(w\mathrm{.}h\mathrm{.}p\mathrm{.})as$n\to\infty$, as shown by Frieze and Suen and by Bollobas, respectively. In this paper we assume in addition that the nodes of the graph are equipped with non-negative weights, independently generated according to some common distribution, and we consider instead the maximum weight of an independent set. Surprisingly, we discover that for certain weight distributions, the limit ${\lim }_n\mathcal{I}(n,c)\mathrm{/}n$ can be computed exactly even when $c>e$, and $\lim_n {\cal I}(n,r)/n$canbecomputedexactlyforsome$r\geq 2$. For example, when the weights are exponentially distributed with parameter 1, $\lim_n {\cal I}(n,2e)/n\approx .5517$,and$\lim_n {\cal I}(n,3)/n\approx .6077$. Our results are established using the recently developed local weak convergence method further reduced to a certain local optimality property exhibited by the models we consider.