Low congestion shortcuts, introduced by Ghaffari and Haeupler (SODA 2016), provide a unified framework for global optimization problems in the congest model of distributed computing. Roughly speaking, for a given graph G and a collection of vertex-disjoint connected subsets S_1,\ldots, S_\ell \subseteq V(G), (c,d) low-congestion shortcuts augment each subgraph G[S_i] with a subgraph H_i \subseteq G such that: (i) each edge appears on at most c subgraphs (congestion bound), and (ii) the diameter of each subgraph G[S_i] \cup H_i is bounded by d (dilation bound). It is desirable to compute shortcuts of small congestion and dilation as these quantities capture the round complexity of many global optimization problems in the congest model. For n-vertex graphs with constant diameter D=O(1), Das-Sarma et al. (STOC 2011, SIAM J. Comput. 2012 ) presented an (implicit) shortcuts lower bound with (As usual, and%DIFDELCMD < \Omega() %%% hide poly-logarithmic factors.) c+d=\Omega(n^{(D-2)/(2D-2)}). A nearly matching upper bound, however, was only recently obtained for D \in \{3,4\} by Kitamura et al. (DISC 2019). In this work, we resolve the long-standing complexity gap of shortcuts in constant diameter graphs, originally posed by Lotker et al. (PODC 2001). We present new shortcut constructions which match, up to poly-logarithmic terms, the lower bounds of Das-Sarma et al. As a result, we provide improved and existentially optimal algorithms for several network optimization tasks in constant diameter graphs, including MST, (1+\epsilon)-approximate minimum cuts and more.
Low congestion shortcuts, introduced by Ghaffari and Haeupler (SODA 2016), provide a unified framework for global optimization problems in the congest model of distributed computing. Roughly speaking, for a given graph G and a collection of vertex-disjoint connected subsets S_1,\ldots, S_\ell \subseteq V(G), (c,d) low-congestion shortcuts augment each subgraph G[S_i] with a subgraph H_i \subseteq G such that: (i) each edge appears on at most c subgraphs (congestion bound), and (ii) the diameter of each subgraph G[S_i] \cup H_i is bounded by d (dilation bound). It is desirable to compute shortcuts of small congestion and dilation as these quantities capture the round complexity of many global optimization problems in the congest model. For n-vertex graphs with constant diameter D=O(1), Elkin (STOC 2004 ) presented an (implicit) shortcuts lower bound with %DIFDELCMD < \Omega() %%% c+d=\Omega(n^{(D-2)/(2D-2)}). A nearly matching upper bound, however, was only recently obtained for D \in \{3,4\} by Kitamura et al. (DISC 2019). In this work, we resolve the long-standing complexity gap of shortcuts in constant diameter graphs, originally posed by Lotker et al. (PODC 2001). We present new shortcut constructions which match, up to poly-logarithmic terms, the lower bounds of Das-Sarma et al. As a result, we provide improved and existentially optimal algorithms for several network optimization tasks in constant diameter graphs, including MST, (1+\epsilon)-approximate minimum cuts and more.
R
Das-Sarma et al. (STOC 2011, SIAM J. Comput. 2012
Elkin (STOC 2004
D
(As usual,
D
and
D
hide poly-logarithmic factors.)