The greedy independent set in a random graph with given degrees

DOI10.1002/RSA.20716MaRDI QIDQ4597601zbMATHOpenAlexFDO

Authors Svante Janson, Graham Brightwell, Malwina Luczak

Publication date 13 December 2017

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

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

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)

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.

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
• A note on the random greedy independent set algorithm

Cited in

(9)

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

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)