On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition
share
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(log n/ϵ) rounds. Ghaffari and Su [SODA `17] made further progress by computing a (1+ϵ) α-forest decomposition in O(log^3 n/ϵ^4) rounds when ϵα = Ω(√(αlog n)), i.e. the limit of their algorithm is an (α+ Ω(√(α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 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^th open question from Barenboim and Elkin's Distributed Graph Algorithms book. Moreover, it gives the first (1+ϵ)α-orientation algorithms with 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.
READ FULL TEXT