# APSP lower bound in graphs with high connectivity

These lower bounds are not reduction from diameter. The basic technique in all these lower bound is the following: We will construct a family of graphs ${\cal F}$ on $n$ vertices with the following properties:
* This family will have some *fixed* edges which will be common to all graphs in the family (denoted by $E_{fix}$).
* There is a cut (with edge set $C$) consisting entirely of edges from $E_{fix}$ through which we will measure the communication. We will assume that one side of this cut will belong to Alice and the other side will belong to Bob.
* The graphs within ${\cal F}$ will be distinguished from each other by the presence or absence of edges in the set $E_{var}$.
* We will argue that Alice needs to send enough amount of information about $E_{var}$ to Bob in order for Bob to know shortest path from his nodes to Alice's nodes approximately. This, combined with an upper bound on the size of $|C|$, will prove the desired lower bound on the round of complexity of the CONGEST algorithm.
* More precisely, we will show that the shortest path from a Bob's vertex to an Alice's vertex will be more than $t_\top$ in the absence of edges in $E_{var}$ and at most $t_\bot$ in the presence of edges in $E_{var}$. This will imply a $(t_\top/t_\bot - \delta)$-approximation lower bound.

## Lower bound for weighted graphs

### $\Omega(n/\lambda)$ lower bound for any approximation


* The set $E_{fix}$ consists of edges $(r, b_j)$ for all $j \in [\lambda]$, edges in the clique $K_n$ and in $K_\lambda$. The weights on these edges are as follows: Edges $(r, b_j)$ gets weights 0, and all other edges get weight $\infty$.
* The set $E_{var}$ consists of edges $(r, v_i)$ for all $i \in [n]$.Suppose we want to prove a $t$-approximation lower bound. The graph family ${\cal F}$ will have a graph for every possible assignment of weights 0 and $t$ on edges in $E_{var}$.
* Suppose the algorithm sends $o(n)$ bits of information to Bob. This means there are at least two assignments which differs on an edge (i.e., on one assignment the edge gets weight 0, and get weight $t$ on the other) which Bob will not be able to distinguish. Let's say that the edge is $(r,v_1)$ wlog. Then Bob does not know if the weight the shortest path from $b_j$ to $v_1$ is 1 or at least $t$. Any $t - \delta$ approximation algorithm should let Bob know such value. Hence, any such algorithm should send at least $\Omega(n)$ bits of information to Bob.

### $\Omega(n)$ lower bound for $(3 - \delta)$-approximation

**Note.** From diameter we can get a $\Omega(n)$ lower bound for $(2-\delta)$ approximation. We cannot hope to get any better this way because there is a $O(\sqrt n + D)$ upper bound for $2$-approximation of diameter in weighted graph. ==Check!==

Consider the following 2-party communication game $APSP_{bp}$: Consider a bipartite graph $\hat G=(U \cup V, E)$ where the edge set is distributed between Alice and Bob such that:
* Alice get set $E_a$, Bob gets set $E_b$ such that
* $E_a \cap E_b = \emptyset$,
* $\hat G[E_a]$ and $\hat G[E_b]$ are connected.
* The goal for Bob to know APSP: Bob wants to know the shortest path between any pair of vertices in $U \times V$ is 1 or at least 3.
* Unless Alice sends the full information about all her edges to Bob, Bob will not be able to know, for any vertex-pair $(u,v) \in U \times V$ such that the edge $(u,v) \notin E_b$, whether the shorted path is of length 1 or of length at least 3.

We will reduce this two party game to distributed setting:
* The vertex set consists of $4n$ vertices equipartitioned into 4 groups: $U, V, U', V'$.
* $E_{fix} = C$ consists of the following matching edges, each with weight 0: 
* Given $E_a$, Alice connects $(u,v) \in E_a$ between $U$ and $V$. Bob connects $(u',v') \in E_b$ between $U'$ and $V'$.
* Given a $(3 - \delta)$-approximation algorithm for APSP, Bob constructs the answer for $APSP_{bp}$ in the following way:
* For any $(u,v) \notin E_b$, Bob checks the shortest path between $(u', v)$. If it is less than 3, Bob answers 1. Otherwise Bob declares the length to be more than 3.
* Clearly, if Alice has the edge $(u,v)$ then the shortest path is $u' \to u \to v$ which is of length 1. If Alice does not have that edge, then the shortest path will be of length at least 3.
* So the total communication from Alice to Bob is $\Omega(n^2)$.

## Lower bound for unweighted graphs

### $\Omega(n/\lambda)$ lower bound for any approximation

**Description of $E_{fix}$:** Consider the following graph:  Each $M_i$ is a clique of size $\lambda$. The vertices of $M_i$ are denoted as $v_i^1, \cdots, v_i^\lambda$.

**Description of $E_{var}$:** Define ${\cal H}_k \subseteq \{0,1\}^n$ to be the set of strings with Hamming weight at least $k$. We define ${\cal F}$ as a bijection from ${\cal H}_\lambda$: For every $z \in {\cal H}_\lambda$, we put a *non-trivial* red path through $M_1, \cdots, M_p$ corresponding the indices where $z$ has a 1, i.e., there is a red path $(v_1^j, \cdots, v_p^j)$ iff $z_j =1$. We denote such a red path as ${\cal P}^j$. For consistency, we assume that when $z_j=0$, then $|{\cal P}^j|=0$ (a *trivial* red path) --- this makes the presentation easier. Let $a^j$ be the vertex at the left end of ${\cal P}^{j}$, i.e., in presence of a non-trivial red path, $a^j = v_1^{j^\ast}$ and $a = v_p^{j^\ast}$ otherwise. At the end of the protocol, Bob wants to know the distance to all $a^j$'s from his vertices. Note that, for $\lambda = o(n)$, the entropy of ${\cal H}_\lambda$ is at least $\Omega(n)$.

Suppose Alice sends $o(n)$ bits of communication though $C$. It means that there are two graphs $G_1, G_2 \in {\cal F}$ which differs on at least 1 non-trivial red path which Bob will be not able to distinguish (Otherwise Bob can decode strings from ${\cal H}_\lambda$ correctly using the bijection between ${\cal H}_\lambda$ and ${\cal F}$ --- a infomration theoretic bottleneck). Let that path be ${\cal P}^{j^\ast}$. Here Bob will not be able to distinguish between the cases where the distance to $a^{j^\ast}$ is $1$ or $p$. Hence any $(p - \delta)$ approximation algorithm should send $\Omega(n)$ bits of information to Bob.

### $\Omega(n)$ lower bound for $(2 - \delta)$-approximation

**Note.** From diameter we can get a $\Omega(n)$ lower bound for $(1.5-\delta)$ approximation. We cannot hope to get any better this way because there is a $O(\sqrt n + D)$ upper bound for $1.5$-approximation of diameter in unweighted graph.

Similar construction as that of $(3- \delta)$-approximation in the weighted case. But, the cut-edges in $C$ will have weight 1 now.

* Given a $(2 - \delta)$-approximation algorithm for APSP, Bob constructs the answer for $APSP_{bp}$ in the following way:
* For any $(u,v) \notin E_b$, Bob checks the shortest path between $(u', v)$. If it is less than 4, Bob answers 1. Otherwise Bob declares the length to be more than 3.
* Clearly, if Alice has the edge $(u,v)$ then the shortest path is $u' \to u \to v$ which is of length 2. If Alice does not have that edge, then the shortest path will be of length at least 4.