The greedy independent set in a random graph with given degrees

DOI10.1002/RSA.20716zbMATH Open1386.05175arXiv1510.05560OpenAlexW2130651739MaRDI QIDQ4597601FDOQ4597601

Authors: Svante Janson, Graham Brightwell, Malwina Luczak 

Publication date: 13 December 2017

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

Abstract: We analyse the size of an independent set in a random graph on $n$ vertices with specified vertex degrees, constructed via a simple greedy algorithm: order the vertices arbitrarily, and, for each vertex in turn, place it in the independent set unless it is adjacent to some vertex already chosen. We find the limit of the expected proportion of vertices in the greedy independent set as $noinfty$, expressed as an integral whose upper limit is defined implicitly, valid whenever the second moment of a random vertex degree is uniformly bounded. We further show that the random proportion of vertices in the independent set converges to the jamming constant as $noinfty$. The results hold under weaker assumptions in a random multigraph with given degrees constructed via the configuration model.

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

Recommendations

• Analysis of greedy algorithms on graphs with bounded degrees
• Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections
• Experimental and Efficient Algorithms
• On independent sets in random graphs
• A note on the random greedy independent set algorithm

zbMATH Keywords

configuration modelgreedy independent setjamming constant

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (9)

• The jamming constant of uniform random graphs
• Corrected mean-field model for random sequential adsorption on random geometric graphs
• Large deviations for the greedy exploration process on configuration models
• Surprising identities for the greedy independent set on Cayley trees
• Analysis of greedy algorithms on graphs with bounded degrees
• Markovian online matching algorithms on large bipartite random graphs
• Greedy maximal independent sets via local limits
• The matching process and independent process in random regular graphs and hypergraphs
• Generalized random sequential adsorption on Erdős-Rényi random graphs

This page was built for publication: The greedy independent set in a random graph with given degrees

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