论文标题
确定性分布式扩展器分解和与分布式降低的应用程序的路由
Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
论文作者
论文摘要
在$ \ mathsf {colest} $模型中利用扩展器的$ \ mathsf {colesest} $模型中，最近有一项令人兴奋的工作。到目前为止，所有这些算法都基于两个工具：扩展器分解和扩展器路由。 $（ε，ϕ）$ - 扩展器分解删除边缘的$ε$分数，以便其余的连接组件至少具有$ ϕ $，即它们是$ ϕ $ - expanders，并且expander fasters允许每个顶点$ v $在$ deffert $ explactand $ expluctand $ thecters $ flost $ \ fertect $ ferte $ \ fertect y vertect（v）邻居。 在本文中，我们为这两个工具提供了第一个有效的确定性分布式算法。我们表明，可以通过$ \ text {poly}（ε^{ - 1}）n^{o（1）} $ rounds $ \ text {poly}（ε^{ - 1}）$（$ n^{o（1）} $ rounds $ \ text = \ text = \ text {poly}（poly}（ε）n^{ - o（o（o（o（o（o））n^{ - o（1）$，并且可以确定eardander rucation的表演， $ \ text {poly}（ϕ^{ - 1}）n^{o（1）} $ rounds。这两种结果都与[Chang和Saranurak，PODC 2019]和[Ghaffari，Kuhn和Su，PODC 2017]的随机算法的先前界限相匹配，直到多种方案。 因此，我们将利用扩展器的现有分布式算法取代。我们表明，可以在$ n^{o（1）} $上的最小跨越树 - 可以在$ n^{o（1）} $ rounds中确定性地构造，并且可以在一般图上确定性地检测和枚举在$ o（n^{0.58}）$ o（n^{0.58}）$ n^$ n^{2/2/3 + O（1）中确定性地求解。 我们还提供了第一个用于在$ \ text {poly}中构建$（ε，ϕ）$ - expander分解的polygarithmic-grogarithmic-rount算法，用于$ \ text {poly}（ε^{ - 1}，\ log n）$ rounds for $ $ n）$ rounds for $ $ n）= 1 / \ text = 1 / \ text {poly}（poly}（ε^ε^{ - 1}} $ n）$。 [Chang and Saranurak，PODC 2019]的先前算法需要$ n^{ω（1）} $ roughs，对于任何$ ϕ \ ge 1/\ text {poly} \ log n $。
There is a recent exciting line of work in distributed graph algorithms in the $\mathsf{CONGEST}$ model that exploit expanders. All these algorithms so far are based on two tools: expander decomposition and expander routing. An $(ε,ϕ)$-expander decomposition removes $ε$-fraction of the edges so that the remaining connected components have conductance at least $ϕ$, i.e., they are $ϕ$-expanders, and expander routing allows each vertex $v$ in a $ϕ$-expander to very quickly exchange $\text{deg}(v)$ messages with any other vertices, not just its local neighbors. In this paper, we give the first efficient deterministic distributed algorithms for both tools. We show that an $(ε,ϕ)$-expander decomposition can be deterministically computed in $\text{poly}(ε^{-1}) n^{o(1)}$ rounds for $ϕ= \text{poly}(ε) n^{-o(1)}$, and that expander routing can be performed deterministically in $\text{poly}(ϕ^{-1})n^{o(1)}$ rounds. Both results match previous bounds of randomized algorithms by [Chang and Saranurak, PODC 2019] and [Ghaffari, Kuhn, and Su, PODC 2017] up to subpolynomial factors. Consequently, we derandomize existing distributed algorithms that exploit expanders. We show that a minimum spanning tree on $n^{o(1)}$-expanders can be constructed deterministically in $n^{o(1)}$ rounds, and triangle detection and enumeration on general graphs can be solved deterministically in $O(n^{0.58})$ and $n^{2/3 + o(1)}$ rounds, respectively. We also give the first polylogarithmic-round randomized algorithm for constructing an $(ε,ϕ)$-expander decomposition in $\text{poly}(ε^{-1}, \log n)$ rounds for $ϕ= 1 / \text{poly}(ε^{-1}, \log n)$. The previous algorithm by [Chang and Saranurak, PODC 2019] needs $n^{Ω(1)}$ rounds for any $ϕ\ge 1/\text{poly}\log n$.
