Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization

There is a recent exciting line of work in distributed graph algorithms in the 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 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.

Using similar techniques, 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). This algorithm is faster than the previous algorithm by [Chang and Saranurak, PODC 2019] in all regimes of parameters. The previous algorithm needs n Ω(1) rounds for any φ ≥ 1/poly log n.