论文标题
KMW绑定的轻松证明
A Breezing Proof of the KMW Bound
论文作者
论文摘要
在2004年的开创性论文中，Kuhn，Moscibroda和Wattenhofer（kmw）证明了本地模型中几个基本图问题的硬度结果：对于任何（随机）算法，有$ n $ nodes和最大程度$δ$的输入图，以及哪些$ nodes $δ$。 n}，\logΔ/\ log \logΔ\}）$（预期）通信回合需要获得最小顶点盖，最小主导集或最大匹配的polyrogarithmic近似值。通过减少，这种硬度扩展到对称性破坏任务，例如查找最大独立集或最大匹配。今天，超过15美元后，仍然没有证据证明这种结果对读者很容易。着眼于这项工作，在这项工作中，我们提供了一个完全独立的和$ \ mathit {simple} $ sufice of KMW下限的证明。关键参数是算法，它依赖于一个不变的，该不变性可以很容易地从下限图的生成规则中验证。
In their seminal paper from 2004, Kuhn, Moscibroda, and Wattenhofer (KMW) proved a hardness result for several fundamental graph problems in the LOCAL model: For any (randomized) algorithm, there are input graphs with $n$ nodes and maximum degree $Δ$ on which $Ω(\min\{\sqrt{\log n/\log \log n},\log Δ/\log \log Δ\})$ (expected) communication rounds are required to obtain polylogarithmic approximations to a minimum vertex cover, minimum dominating set, or maximum matching. Via reduction, this hardness extends to symmetry breaking tasks like finding maximal independent sets or maximal matchings. Today, more than $15$ years later, there is still no proof of this result that is easy on the reader. Setting out to change this, in this work, we provide a fully self-contained and $\mathit{simple}$ proof of the KMW lower bound. The key argument is algorithmic, and it relies on an invariant that can be readily verified from the generation rules of the lower bound graphs.
