# Broadcast congested clique

We are first looking at APSP in BCC (Broadcast congested-clique).

## $(2 + o(1))$ approximation from Nan14

This is from [Nan14](https://arxiv.org/pdf/1403.5171.pdf). We first define a few things: Consider a weighted graph $(G,w)$.
* $dist^h(u,v) = \min_\text{path P with h edges}w(P)$ if such a path $P$ exists between $u$ and $v$.
* $spdist(u,v)$: minimum $h$ such that $dist^h(u,v) = dist(u,v)$.
* $SPDiam(G,w)$ is the maximum $spdist(u,v)$.
* $S^k(u) \subseteq V(G)$: The set of exactly $k$ vertices nearest to $u$ (excluding $u$).
* For any $v \in S^k(u)$ and $v' \notin S^k(u)$, $dist(u,v) \leq dist(u,v')$.
* $E^k(u)$: Set of exactly $k$ edges of minimum weight incident on $u$. :bangbang: This is not the set which connects $S^k(u)$ to $u$. :bangbang:
* $(G^k, w)$: Subgraph containing only $E^k(u)$ for all $u \in V$.
* $(G,w)^k$: **$k$-shortcut graph** of $(G,w)$ where an edge $(u,v)$ is added for all $u \in V, v \in S^k(u), w(u,v) = dist(u,v)$.

**Theorem.** $SPDiam((G,w)^k) < 4n/k$.

**Theorem.** For any node $u$:
* $S^k_{G,w}(u) = S^k_{G^k,w}(u)$,
* ==This implies that if any vertex knows the edges in $E^k(u)$ for all $u$, then it can compute $S^k(u)$ for all $u$.==
* $dist_G(u,v) = dist_{G^k}(u,v)$ for any $v \in S^k_G(u)$.
* ==This implies that if any vertex knows the edges in $E^k(u)$ for all $u$ and their weights, then it can compute all **shortcut edges** in $(G,w)^k$.==

*Proof sketch.* Run Dijkstra's algorithm.

The algorithms runs in two phases:
* Phase 1(a).
Every node $u$ broadcasts $E^k(u)$. Having this, every vertex $v$ can compute $S^k(v)$ and can obtain shortcut edges incident on $v$ in $(G,w)^k$.
* This makes sure: $SPDiam((G,w)^k) < 4n/k$ and $dist_{(G,w)}(u,v) = dist_{(G,w)^k}(u,v)$. ==To see this, consider the shortest path from $u$ to $v$ in $G$. The shortcuts do not change the distance, even though they change the number of hops.==

* Phase 1(b).
Every node $u$ broadcasts $S^k(u)$ and distance of all $z \in S^k(u)$ from $u$. Then every node $v$ runs an local relaxation to maintain the following: $w'(u,v) \leq \min_{z \in S^k(u)} dist(u,z) + w(z,v)$.

* Phase 2. (Hitting set)
Pick $n/k$ many random centers and run shortest path algorithm up to $k$ hops from all of them in $(G,w)^k$. **This can be done in $O(k + n/k)$ time in BCC(as communication diameter is 1). In CONGEST, it will require $O(k + n/k + D)$ time where $D$ is the diameter of the graph.** ==See Nan14. Also this works even for **CONGEST**.==
* At the termination, every node $u$ knows $(1 + o(1))$-approximation of distance to every source.==This may seem weird! But, note that, with shortcuts, every source is within $k$-hop from any vertex.==
* Each node $u$ also knows $w'(u,v)$ for all $v \in V$, and also $w'(x,y)$ for $x \neq u$ and $y \in S^k(x)$ which $u$ got from $x$ via broadcasting.
* Having this, $u$ can compute $(2 + o(1))$-approximate distance to any node $v$. ==See Nan14==

Setting $k = \sqrt n$, this gives $\sqrt n$ algorithm in BCC.

==Note!== This is not really a BCC protocol... Explain.

---
This is what we have so far.

| | Column 2 | Column 3 |
| -------- | -------- | -------- |
| $5 + \epsilon$ | Text | Text |
| $5 - \epsilon$ | Text | Text |
| $3 + \epsilon$ | Text | Text |
| $3 - \epsilon$ | Text | Text |

## Min-cut

* Directed min-cut
* weighted min-cut