A Simple Average-case Analysis of Recursive Randomized Greedy MIS
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908932993187840 |
|---|---|
| author | Dalirrooyfard, Mina Makarychev, Konstantin Mitrović, Slobodan |
| author_facet | Dalirrooyfard, Mina Makarychev, Konstantin Mitrović, Slobodan |
| contents | 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 upper bounded 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.
Our analysis is inspired by the recent work of Dalirrooyfard, Makarychev, and Mitrović (2024), who developed a potential-function-based argument to analyze a new algorithm for correlation clustering. We adapt this approach to the MIS setting, yielding a more direct and arguably more transparent analysis of the recursive randomized greedy MIS algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_01462 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Simple Average-case Analysis of Recursive Randomized Greedy MIS Dalirrooyfard, Mina Makarychev, Konstantin Mitrović, Slobodan Data Structures and Algorithms 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 upper bounded 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. Our analysis is inspired by the recent work of Dalirrooyfard, Makarychev, and Mitrović (2024), who developed a potential-function-based argument to analyze a new algorithm for correlation clustering. We adapt this approach to the MIS setting, yielding a more direct and arguably more transparent analysis of the recursive randomized greedy MIS algorithm. |
| title | A Simple Average-case Analysis of Recursive Randomized Greedy MIS |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.01462 |