← 研踪 PaperTrailarXiv:2611.10215 · v1
Randomized Greedy MIS Is Fast at Every Node of a Tree
首次提交 2026-11-07 05:01
版本更新 2026-11-07 05:01
雷达观测 2026-11-10 10:11
摘要
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 , to determine whether belongs to the MIS, recursively evaluate the neighbors of that precede in the random order. If any such neighbor is found to belong to the MIS, the procedure immediately concludes that is not in the MIS; otherwise, it concludes that is in the MIS. For graphs of maximum degree , Nguyen and Onak showed that, in expectation over the random ordering, this procedure makes 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 recursive calls in expectation.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-07 05:01 · 最新观测版本
Randomized Greedy MIS Is Fast at Every Node of a Tree
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 , to determine whether belongs to the MIS, recursively evaluate the neighbors of that precede in the random order. If any such neighbor is found to belong to the MIS, the procedure immediately concludes that is not in the MIS; otherwise, it concludes that is in the MIS. For graphs of maximum degree , Nguyen and Onak showed that, in expectation over the random ordering, this procedure makes 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 recursive calls in expectation.
查看此版本解读 →查看此版本原文 ↗