跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 vv, to determine whether vv belongs to the MIS, recursively evaluate the neighbors of vv that precede vv in the random order. If any such neighbor is found to belong to the MIS, the procedure immediately concludes that vv is not in the MIS; otherwise, it concludes that vv 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⁡(Δ))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 poly(Δ)\mathrm{poly}(Δ) recursive calls in expectation.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 vv, to determine whether vv belongs to the MIS, recursively evaluate the neighbors of vv that precede vv in the random order. If any such neighbor is found to belong to the MIS, the procedure immediately concludes that vv is not in the MIS; otherwise, it concludes that vv 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⁡(Δ))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 poly(Δ)\mathrm{poly}(Δ) recursive calls in expectation.

查看此版本解读 →查看此版本原文 ↗