# Low-congestion shortcuts

The content is from the following two papers: [GH16](https://pdfs.semanticscholar.org/d7d1/bfd55973cef5fd93d4398cf997e584d75e69.pdf)[^1] and [HIZ16](https://arxiv.org/pdf/1607.07553.pdf)[^2].

[TOC]
## Definition.
* Given graph $G$ and a partition $S_1, \cdots, S_k$ of vertices where each $S_i$ induces a connected subgraph,
* Define $H_1, \cdots, H_k$, $H_i$ possibly empty, to be shortcuts with $\alpha$-congestion and $\beta$-dilation if
* For each $i \in [k]$, diameter of $G(S_i) \cup H_i$ is at most $\beta$, and
* Each edge $e \in E(G)$ takes part in at most $\alpha$ many $G(S_i) \cup H_i$.

Define quality of a short-cut to be $Q = \alpha + \beta$. We are generally interested in how good the quality $Q$ of shortcut is over worst-case partition of the graph.

*Note.* As $S_i$'s are disjoint, any $e \in S_i$ will acquire congestion only from other $H_j$'s.

## Trivialities

For any graph, we can find the following shortcuts:

* $\alpha = 1, \beta = n \Rightarrow Q=n$: Here $H_i = \emptyset$ for all $i$.
* $\alpha = k, \beta = D \Rightarrow Q=n$: Here $G(S_i) \cup H_i = G$ for all $i$.

A little non-trivial claim, which achieves the middle ground, is the following:

**Claim.** Any graph $G$ has shortcut with $\alpha = \sqrt n$ and $\beta = D + \sqrt n$.

*Proof.* For $S_i$ such that $|S_i| \leq \sqrt n$, set $H_i = \emptyset$ and for other $S_i$, set $G(S_i) \cup H_i = G$. Each edge can take part is at most one small $S_i$ and at most $\sqrt n$ $H_j$'s for large $S_j$. Also, the diameter of each $S_i$ is bounded by $D + \sqrt n$.

## Result of GH16

The result of GH16 has three parts.

**Part 1: Existential.**

**Theorem (Easy-version).** For any planar graph $G$, there is a worst-case short-cut of $\alpha = O(D)$ and $\beta = O(D^2)$.

**Theorem (Hard-version).** For any planar graph $G$, there is a worst-case short-cut of $\alpha = O(D \log D)$ and $\beta = O(D \log D)$.

**Theorem (Lower bound).** There is a graph $G$ and partition of $V$ into $S_1, \cdots, S_k$ such that any shortcut will have $Q = \Omega(\frac{D \log D}{\log \log D})$.

**Part 2. Constructive.**

**Theorem.** For any planar graph, the $(D \log D)$-congestion $(D \log D)$-dilation shortcut can be found in $\tilde O(D)$ time in a distributed fashion.

**Part 3. Application.**

**Theorem (MST).** For any planar graph, there is a $\tilde O(D)$-round MST algorithm.

**Theorem (Approx min-cut).** For any planar graph, there is a $\tilde O(D)$-round $(1 + \epsilon)$-approx min-cut algorithm.

### Part-wise aggregration

**Problem definition.**
* Given $G$ and a partition of $V$ in $S_1, \cdots, S_k$ (connected-components),
* Compute a simple aggregrate function in each part $S_i$, e.g., min-value.

The ==main challenge== is that, for individual $S_i$, the diameter can be large.

Assuming we have $(\alpha, \beta)$-shortcuts we can do the following:
1. **Routing:** Compute BFS tree for routing. This tree has depth $\beta = \tilde O(D)$. We will broadcast along this tree.
2. **Scheduling**. Each edge can have congestion $\alpha = \tilde O(D)$. If we do naive scheduling, we get round complexity of $\alpha \cdot \beta = \tilde O(D^2)$. We can use ==random delay== to decrease the complexity to $(\alpha + \beta) \log n \approx \tilde O(D)$.

### MST computation

We will modify Boruvka's MST algorithm.

Start with T = 0
Repeat log n times
    Compute low-congestion shortcut for connected components,
    Aggregrate cost and identify the cheapest outgoing edge from every component,
    Add these edges to T

Each loop need time $(\alpha + \beta)\log n$ for aggregration. For $\alpha, \beta = \tilde O(D)$, this shortcut can be computed in $\tilde O(D)$ rounds. So the total time complexity is $\tilde O(D \log n)$.

# Tree-restricted shortcut

[^1]:{%pdf https://pdfs.semanticscholar.org/d7d1/bfd55973cef5fd93d4398cf997e584d75e69.pdf %}

[^2]:{%pdf https://arxiv.org/pdf/1607.07553.pdf %}