论文标题
裁定集的分布式下限
Distributed Lower Bounds for Ruling Sets
论文作者
论文摘要
给定图形$ g =（v，e）$，$（α，β）$ - 统治集是一个子集$ s \ subseteq v $，使得$ s $中任何两个顶点之间的距离至少为$ v $ in $ v $的任何顶点与$ s $中最接近$ s $的距离。我们提出了分布式计算统治集的下限。 更确切地说，对于计算$（2，β）$的问题 - 在本地模型中设定的统治，我们显示以下内容，其中$ n $表示顶点的数量，$δ$的最高度，$ c $是$ n $和$δ$的普遍常数。 $ \ bullet $任何确定性算法都需要$ω\ left（\ min \ left \ {\ frac {\ frac {\logδ} {β\ log \ log \ log \ logueδ}，\log_Δn\ right \ right \ right \ right \ right \ right \ right \ right \ \ right \ prirct \ right \ right \ right）$。 \ sqrt {\ frac {\logδ} {\ log \ logulauΔ}}，\log_Δn\ right \} $。通过优化$δ$，这意味着$ω\ left的确定性下限（\ sqrt {\ frac {\ frac {\ log n} {β\ log \ log \ log \ log \ log n}} \ right）$ for $β\ le c \ le c \ le c \ sqrt [3] $ \ bullet $任何随机算法都需要$ω\ left（\ min \ left \ {\ frac {\logδ} {β\ log \ log \ log \logΔ}，\log_Δ\log_Δ\ log n \ right \ right \ right \ right \ right \ right \ right \ right \ right \ right \ right） \ sqrt {\ frac {\logΔ} {\ log \ logulaΔ}}，\log_Δ\ log n \ right \} $。通过优化$δ$，这意味着$ω\ left的随机下限（\ sqrt {\ frac {\ frac {\ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log n}} \ right）$ for $β\ le c \ sqrt [3] n}} $。 对于$β> 1 $，这在先前最佳的$ω（\ log^* n）$ rounds的最佳下限上得到了改善，这是从30年历史的hinial [focs'87]和naor [j.disc.math.'91]的界限中提高的。对于$β= 1 $，即，对于计算最大独立集的问题，我们的结果改善了树木上$ω（\ log^* n）$的先前最佳下限，因为我们的边界已经在树上保持。
Given a graph $G = (V,E)$, an $(α, β)$-ruling set is a subset $S \subseteq V$ such that the distance between any two vertices in $S$ is at least $α$, and the distance between any vertex in $V$ and the closest vertex in $S$ is at most $β$. We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a $(2, β)$-ruling set in the LOCAL model, we show the following, where $n$ denotes the number of vertices, $Δ$ the maximum degree, and $c$ is some universal constant independent of $n$ and $Δ$. $\bullet$ Any deterministic algorithm requires $Ω\left(\min \left\{ \frac{\log Δ}{β\log \log Δ} , \log_Δn \right\} \right)$ rounds, for all $β\le c \cdot \min\left\{ \sqrt{\frac{\log Δ}{\log \log Δ}} , \log_Δn \right\}$. By optimizing $Δ$, this implies a deterministic lower bound of $Ω\left(\sqrt{\frac{\log n}{β\log \log n}}\right)$ for all $β\le c \sqrt[3]{\frac{\log n}{\log \log n}}$. $\bullet$ Any randomized algorithm requires $Ω\left(\min \left\{ \frac{\log Δ}{β\log \log Δ} , \log_Δ\log n \right\} \right)$ rounds, for all $β\le c \cdot \min\left\{ \sqrt{\frac{\log Δ}{\log \log Δ}} , \log_Δ\log n \right\}$. By optimizing $Δ$, this implies a randomized lower bound of $Ω\left(\sqrt{\frac{\log \log n}{β\log \log \log n}}\right)$ for all $β\le c \sqrt[3]{\frac{\log \log n}{\log \log \log n}}$. For $β> 1$, this improves on the previously best lower bound of $Ω(\log^* n)$ rounds that follows from the 30-year-old bounds of Linial [FOCS'87] and Naor [J.Disc.Math.'91]. For $β= 1$, i.e., for the problem of computing a maximal independent set, our results improve on the previously best lower bound of $Ω(\log^* n)$ on trees, as our bounds already hold on trees.
