论文标题
在纳什 - 威廉姆斯森林分解和星林分解的地方
On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition
论文作者
论文摘要
给定图形$ g =（v，e）$带有树木$α$，我们研究了将$ g $的边缘分解为分布式本地模型中$（1+ε）α$分离森林的问题。 Barenboim和Elkin [PODC`08]给出了一种局部算法，该算法使用$ O（\ frac {\ log n}ε）$ rounds计算$（2+ε）α$ Forest分解。 Ghaffari和Su [Soda``17]通过计算$ O（\ frac {\ frac {\ log^3 n} {ε^4}）$ rounds $ o（\ frac {\ frac {\ log^3 n}）$ rounds的$（1+ε）α$ - forest分解的进一步进展，当时取得了进一步的进步。 ω（\ sqrt {α\ log n}））$ - 森林分解。该算法基于Alon，McDiarmid \＆Reed [Combinatorica`92]的组合结构，实际上将图形分解为\ emph {star-forests}，即每个森林都是恒星的集合。 本文中我们的主要结果是减少$εα$在$（1+ε）α$ forest分解和恒星 - 森林分解中的阈值。这进一步回答了$ 10^{\ text {th}} $从Barenboim和Elkin的“分布式图形算法”书中打开问题。此外，它在$ε^{ - 1} $上给出了第一个$（1+ε）α$ - 方向算法。 在很高的水平上，我们的森林分解结果基于网络分解，负载平衡和对局部增强序列的新结构结果的组合。我们对星林分解的结果使用了更仔细的概率分析来构建Alon，McDiarmid，\＆Reed；这里的星际企业的界限以前尚不清楚，甚至是非结构性的。
Given a graph $G=(V,E)$ with arboricity $α$, we study the problem of decomposing the edges of $G$ into $(1+ε)α$ disjoint forests in the distributed LOCAL model. Barenboim and Elkin [PODC `08] gave a LOCAL algorithm that computes a $(2+ε)α$-forest decomposition using $O(\frac{\log n}ε)$ rounds. Ghaffari and Su [SODA `17] made further progress by computing a $(1+ε) α$-forest decomposition in $O(\frac{\log^3 n}{ε^4})$ rounds when $εα= Ω(\sqrt{α\log n})$, i.e. the limit of their algorithm is an $(α+ Ω(\sqrt{α\log n}))$-forest decomposition. This algorithm, based on a combinatorial construction of Alon, McDiarmid \& Reed [Combinatorica `92], in fact provides a decomposition of the graph into \emph{star-forests}, i.e. each forest is a collection of stars. Our main result in this paper is to reduce the threshold of $εα$ in $(1+ε)α$-forest decomposition and star-forest decomposition. This further answers the $10^{\text{th}}$ open question from Barenboim and Elkin's "Distributed Graph Algorithms" book. Moreover, it gives the first $(1+ε)α$-orientation algorithms with {\it linear dependencies} on $ε^{-1}$. At a high level, our results for forest-decomposition are based on a combination of network decomposition, load balancing, and a new structural result on local augmenting sequences. Our result for star-forest decomposition uses a more careful probabilistic analysis for the construction of Alon, McDiarmid, \& Reed; the bounds on star-arboricity here were not previously known, even non-constructively.
