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

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

2003-09-26

arxiv.org/abs/math/0309441v1

Mathematics

Probability

31 pages

Scientific paper

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 ${\cal I}(n,r)$ and ${\cal I}(n,c)$ be the sizes of the largest independent set in $G(n,c/n)$ and $G_r(n)$. The asymptotic value of ${\cal I}(n,c)/n$ as $n\to\infty$, can be computed using the Karp-Sipser algorithm when $c\leq 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$ with high probability (w.h.p.) 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 {\cal I}(n,c)/n$ can be computed exactly even when $c>e$, and $\lim_n {\cal I}(n,r)/n$ can be computed exactly for some $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.

Affiliated with

Also associated with

No associations

Rating

Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results using the Local Weak Convergence Method does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results using the Local Weak Convergence Method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results using the Local Weak Convergence Method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-565673