Premium
A note on the random greedy independent set algorithm
Author(s) -
Bennett Patrick,
Bohman Tom
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20667
Subject(s) - combinatorics , hypergraph , mathematics , independent set , vertex (graph theory) , discrete mathematics , set (abstract data type) , greedy algorithm , algorithm , computer science , graph , programming language
Let r be a fixed constant and let H be an r ‐uniform, D ‐regular hypergraph on N vertices. Assume further that D > N ϵfor some ϵ > 0 . Consider the random greedy algorithm for forming an independent set in H . An independent set is chosen at random by iteratively choosing vertices at random to be in the independent set. At each step we chose a vertex uniformly at random from the collection of vertices that could be added to the independent set (i.e. the collection of vertices v with the property that v is not in the current independent set I and I ∪ { v } contains no edge in H ). Note that this process terminates at a maximal subset of vertices with the property that this set contains no edge of H ; that is, the process terminates at a maximal independent set. We prove that if H satisfies certain degree and codegree conditions then there are Ω ( N · ( ( log N ) / D )1 r − 1)vertices in the independent set produced by the random greedy algorithm with high probability. This result generalizes a lower bound on the number of steps in the H ‐free process due to Bohman and Keevash and produces objects of interest in additive combinatorics. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 479–502, 2016