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 widetildeO(1) rounds) for problems that are closely related to hard global problems (i.e., with a lower bound of Omega(Diamsqrtn) rounds).  :52,main results are:  :56,For Ddiameter 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, STOCu002719.  :56,For Ddiameter unweighted :94,graphs, we present a deterministic algorithm that computes of all edge connectivities up to constant in poly(D)cdot 2O(sqrtlog nloglog n) rounds.  :119,Computation of sparse lambda connectivity certificates in widetildeO(lambda) rounds. Previous constructions where known only for lambda leq 3 and required O(D) rounds. This resolves the problem raised by Dori PODCu002718.

LowCongestion Shortcut and Graph Parameters. The concept of lowcongestion shortcuts is initiated by Ghaffari and Haeupler SODA2016 for addressing the design of CONGEST algorithms running fast in restricted network topologies. Specifically, given a specific graph class X, an fround algorithm of constructing shortcuts of quality q for any instance in X results in tildeO(q  f)round algorithms of solving several fundamental graph problems such as minimum spanning tree and minimum cut, for X.  :68,this paper, we consider the relationship between the quality of lowcongestion shortcuts and three major graph parameters, chordality, diameter, and cliquewidth. The main contribution of the paper is threefold: (1) We show an O(1)round algorithm which constructs a lowcongestion shortcut with quality O(kD) for any kchordal graph, and prove that the quality and running time of :68,this construction is nearly optimal up to polylogarithmic factors. (2) We present two algorithms, each of which constructs a lowcongestion shortcut with quality tildeO(n14) in tildeO(n14) rounds for graphs of D3, and that with quality tildeO(n13) in tildeO(n13) rounds for graphs of D4 respectively. These results obviously deduce two MST algorithms running in tildeO(n14) and tildeO(n13) rounds for D3 and 4 respectively, which almost close the longstanding complexity gap of the MST construction in smalldiameter graphs originally posed by Lotker et al. Distributed Computing 2006. (3) We show that bounding cliquewidth does not help the construction of good shortcuts by presenting a network topology of cliquewidth six where the construction of MST is as expensive as the general case.