Distributed algorithms for planar networks II: low-congestion shortcuts, MST, and Min-Cut

ABSTRACT

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 S₁, . . ., S_N, each inducing a connected subgraph G[S_i]. We define an α-congestion shortcut with dilation β to be a set of subgraphs H₁, . . ., H_N ⊆ G, one for each subset S_i, such that

1. For each i ∈ [1, N], the diameter of the subgraph G[S_i] + H_i is at most β.

2. For each edge e ∈ E, the number of subgraphs G[S_i] + H_i 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, max{α, β} = Ω(D[EQUATION]).

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 Ω(D + [EQUATION]) 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.

References

References are not available

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

• Theory of computation