Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method

DOI10.1002/RSA.20072MaRDI QIDQ3376664zbMATH OpenOpenAlexFDO

Authors David Gamarnik, Tomasz Nowicki, Grzegorz Świrszcz

Publication date 24 March 2006

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0309441

zbMATH Keywords

random graphmaximum weight independent setmaximum weight matching

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: 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 $calI(n,r)$ and $calI(n,c)$ be the sizes of the largest independent set in $G(n,c/n)$ and $G_r(n)$. The asymptotic value of $calI(n,c)/n$ as $noinfty$, can be computed using the Karp-Sipser algorithm when $cleqe$. For random cubic graphs, $r=3$, it is only known that $.432leqlimin{f}_{n}calI(n,3)/nleqlimsu{p}_{n}calI(n,3)leq.4591$ with high probability (w.h.p.) as $noinfty$, 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 $li{m}_{n}calI(n,c)/n$ can be computed exactly even when $c>e$, and $li{m}_{n}calI(n,r)/n$ can be computed exactly for some $rgeq2$. For example, when the weights are exponentially distributed with parameter 1, $li{m}_{n}calI(n,2e)/napprox.5517$, and $li{m}_{n}calI(n,3)/napprox.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.

Recommendations

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract)
• Finding a Maximum Independent Set in a Sparse Random Graph
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Independent sets in random graphs from the weighted second moment method
• Maximum independent sets on random regular graphs
• Independent sets in random sparse graphs
• Randomly finding independent sets in locally sparse graphs
• scientific article; zbMATH DE number 1139976

Cites work

• scientific article; zbMATH DE number 734955 (Why is no real title available?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs

Cited in

(21)

• The densest subgraph problem in sparse random graphs
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
• A survey on performance analysis of warehouse carousel systems
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
• On maximal hard-core thinnings of stationary particle processes
• Replica symmetry of the minimum matching
• Endogeny for the logistic recursive distributional equation
• Dismantling Sparse Random Graphs
• Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections
• Limits of discrete distributions and Gibbs measures on random graphs
• Invariant probability measures and dynamics of exponential linear type maps
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Weighted enumeration of spanning subgraphs in locally tree-like graphs
• Large deviations of the greedy independent set algorithm on sparse random graphs
• Strong and weighted matchings in inhomogenous random graphs
• First-passage percolation on a ladder graph, and the path cost in a VCG auction
• Server waiting times in infinite supply polling systems with preparation times
• The planted matching problem: phase transitions and exact results
• Sparse graphs: metrics and random models

This page was built for publication: Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3376664)