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

Original · EN

Let G(n,c/n) and Gᵣ(n) be an n-node sparse random graph and a sparse random r-regular graph, respectively, and let I(n,r) and I(n,c) be the sizes of the largest independent set in G(n,c/n) and Gᵣ(n). The asymptotic value of I(n,c)/n as n→∞, can be computed using the Karp-Sipser algorithm when c≤ e. For random cubic graphs, r=3, it is only known that.432≤ₙ I(n,3)/n ≤ ₙ I(n,3)≤.4591 with high probability (w.h.p.) as n→∞, 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 ₙ I(n,c)/n can be computed exactly even when c>e, and ₙ I(n,r)/n can be computed exactly for some r≥ 2. For example, when the weights are exponentially distributed with parameter 1, ₙ I(n,2e)/n≈.5517, and ₙ I(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.