Randomized greedy algorithm runs efficiently at every node in tree graphs
Randomized Greedy MIS Is Fast at Every Node of a Tree
Data Structures and Algorithms
Summary
This paper studies a simple way to pick a large set of points in a network so that none are connected to each other. The method uses a random order and checks neighbors to decide if a point can be included. While it was known that this method works well on average in some networks, the authors prove it actually runs efficiently starting from any point in tree-shaped networks. This means the process doesn't get stuck in complicated loops and finishes quickly no matter where it starts in these networks.
What this means in practice
- •For distributed system engineers: Optimize local decision algorithms in tree-structured networks by enabling efficient checks for node inclusion without expensive recursion.
- •For network algorithm developers: Design faster sublinear-time algorithms for problems like matching and vertex cover in networks with tree-like topology.
A theory result. No direct application yet.
Authors
Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović, Srikkanth Ramachandran
Abstract
The Randomized Greedy MIS (RGMIS) algorithm computes a maximal independent set (MIS) by processing the vertices in a uniformly random order and greedily adding each vertex to the independent set whenever possible. Despite its simplicity, this algorithm has proved effective in a range of parallel, distributed, and dynamic settings. For sufficiently small maximum degree, Nguyen and Onak (FOCS~'08) and Yoshida, Yamamoto, and Ito (STOC~'09) showed that a recursive simulation of RGMIS can be used to estimate the sizes of matching and vertex cover in sublinear time. The key subroutine in their approach is the following local query procedure: given a vertex $v$, to determine whether $v$ belongs to the MIS, recursively evaluate the neighbors of $v$ that precede $v$ in the random order. If any such neighbor is found to belong to the MIS, the procedure immediately concludes that $v$ is not in the MIS; otherwise, it concludes that $v$ is in the MIS. For graphs of maximum degree $Δ$, Nguyen and Onak showed that, in expectation over the random ordering, this procedure makes $O(\exp(Δ))$ recursive calls from a worst-case starting vertex. No better upper bound is known even for trees. We prove that on trees, from \textit{any} starting vertex, this recursive RGMIS procedure makes $\mathrm{poly}(Δ)$ recursive calls in expectation.