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 (

*n, r*) and (

*n, c*) be the sizes of the largest independent set in G(

*n, c/n*) and

G

*(*

_{r}*n*). The asymptotic value of (

*n, c*)/

*n*as , can be computed using the Karp-Sipser algorithm when

*c*

*e*. For random cubic graphs,

*r*= 3, it is only known that .432 lim inf

*(*

_{n}*n*, 3)/

*n*lim sup

*(*

_{n}*n*, 3)/

*n*

*.4591 with high probability (w.h.p.) as , as shown in [FS94] and [Bol81], respectively.*

In this paper we assume in addition that the nodes of the graph are equipped with nonnegative 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}*n, c*)/

*n*can be computed exactly even when

*c*>

*e*, and lim

*(*

_{n}*n, r*)/n can be computed exactly for some

*r*2. For example, when the weights are exponentially distributed with parameter 1, lim

*(*

_{n}*n*, 2

*e*)/

*n*.5517, and lim

*(*

_{n}*n*, 3)/

*n*

*.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. Using the developed technique we show in addition that in the unweighted case lim inf

*(*

_{n }*n*, 4)/

*n*.3533, which is a new lower bound. We also prove that in any (non-random) graph with degree 3 and large girth, the size of the largest independent set is at least .3923

*n*

*o*(

*n*), improving the previous bound (7/18)

*n*

*o*(

*n*) in [HS82]. Finally, we extend our results to maximum weight matchings in G(

*n, c/n*) and G

_{r}(

*n*). For the case of exponential distributions, we compute the corresponding limits for every

*c*> 0 and every

*r*

*2.*

By:* David Gamarnik, Tomasz Nowicki, Grzegorz Swirszcz*

Published in: Lecture Notes in Computer Science, volume 3122, (no ), pages 357-68 in 2004

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .