Small Cuts and Connectivity Certificates: A Fault Tolerant Approach

We revisit classical connectivity problems in the CONGEST model of distributed computing. By using techniques from fault tolerant network design, we show improved constructions, some of which are even "local" (i.e., with $\widetilde{O}(1)$ rounds) for problems that are closely related to hard global problems (i.e., with a lower bound of $Ω(Diam+\sqrt{n})$ rounds). Our main results are: (1) For $D$-diameter unweighted graphs with constant edge connectivity, we show an exact distributed deterministic computation of the minimum cut in $poly(D)$ rounds. This resolves one the open problems recently raised in Daga, Henzinger, Nanongkai and Saranurak, STOC'19. (2) For $D$-diameter unweighted graphs, we present a deterministic algorithm that computes of all edge connectivities up to constant in $poly(D)\cdot 2^{O(\sqrt{\log n\log\log n})}$ rounds. (3) Computation of sparse $λ$ connectivity certificates in $\widetilde{O}(λ)$ rounds. Previous constructions where known only for $λ\leq 3$ and required $O(D)$ rounds. This resolves the problem raised by Dori PODC'18.