Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
Mohsen Ghaffari, Bernhard Haeupler · 2015
This paper introduces the concept of low-congestion shortcuts for (near-)planar networks, and demonstrates their power by using them to obtain near-optimal distributed algorithms for problems such as Minimum Spanning Tree (MST) or Minimum Cut, in planar networks. Consider a graph G = (V, E) and a partitioning of V into subsets of nodes S1, …, SN, each inducing a connected subgraph G[Si]. We define an α-congestion shortcut with dilation β to be a set of subgraphs H1, …, HN ⊆ G, one for each subset Si, such that 1. For each i ∊ [1, N], the diameter of the subgraph G[Si] + Hi is at most β. 2. For each edge e ∊ E, the number of subgraphs G[Si] + Hi containing e is at most α. We prove that any partition of a D-diameter planar graph into individually-connected parts admits an O(D log D)-congestion shortcut with dilation O(D log D), and we also present a distributed construction of it in Õ(D) rounds. We moreover prove these parameters to be near-optimal; i.e., there are instances in which, unavoidably, . Finally, we use low-congestion shortcuts, and their efficient distributed construction, to derive Õ(D)-round distributed algorithms for MST and Min-Cut, in planar networks. This complexity nearly matches the trivial lower bound of Ω(D). We remark that this is the first result bypassing the well-known existential lower bound of general graphs (see Peleg and Rubinovich [FOCS'99]; Elkin [STOC'04]; and Das Sarma et al. [STOC'11]) in a family of graphs of interest.