Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
share
There is a recent exciting line of work in distributed graph algorithms in the 𝖢𝖮𝖭𝖦𝖤𝖲𝖳 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 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 poly(ϵ^-1) n^o(1) rounds for ϕ = poly(ϵ) n^-o(1), and that expander routing can be performed deterministically in 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 poly(ϵ^-1, log n) rounds for ϕ = 1 / poly(ϵ^-1, log n). The previous algorithm by [Chang and Saranurak, PODC 2019] needs n^Ω(1) rounds for any ϕ≥ 1/polylog n.
READ FULL TEXT