A Simple Average-case Analysis of Recursive Randomized Greedy MIS
Abstract
We revisit the complexity analysis of the recursive version of the randomized greedy algorithm for computing a maximal independent set (MIS), originally analyzed by Yoshida, Yamamoto, and Ito (2009). They showed that, on average per vertex, the expected number of recursive calls made by this algorithm is upperbounded by the average degree of the input graph. While their analysis is clever and intricate, we provide a significantly simpler alternative that achieves the same guarantee.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Stochastic Gradient Optimization Techniques
Advanced Graph Theory Research
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 241–246
- Publication date
- 1 January 2026
- Language
- EN