Paper Info

Title | ||
---|---|---|

Low-Congestion Shortcuts in Constant Diameter Graphs |

Abstract | ||
---|---|---|

ABSTRACTLow 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 S1,…,Sℓ ⊆V(G), (c,d) low-congestion shortcuts augment each subgraph G[Si] with a subgraph Hi ⊆G such that: (i) each edge appears on at most c subgraphs (congestion bound), and (ii) the diameter of each subgraph G[Si] ∪ Hi 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 with1 c + d + Ωe (n (D-2)/(2D-2)). A nearly matching upper bound, however, was only recently obtained for D ∈ {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 Elkin. As a result, we provide improved and existentially optimal algorithms for several network optimization tasks in constant diameter graphs, including MST, (1+ε)-approximate minimum cuts and more. |

Year | DOI | Venue |
---|---|---|

2021 | 10.1145/3465084.3467927 | Principles of Distributed Computing |

Keywords | DocType | Citations |

Congest Model, Global Network Optimization, Shortcuts | Conference | 0 |

PageRank | References | Authors |

0.34 | 0 | 2 |

Authors (2 rows)

Cited by (0 rows)

References (0 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Shimon Kogan | 1 | 67 | 6.60 |

Merav Parter | 2 | 169 | 32.59 |