# Graphs with high min-cut

<!---
* Problem to consider: APSP. Goal complexity: ??
* Conductance is not comparable to min-cut
* Tree packing, but each tree can have high diameter.
* What kind of shortcut we need?
--->
We are looking at graphs with good connectivity.
* The naive example is where the graph is a clique, which boils down to the model of CONGESTED-CLIQUE.
* When the graph is an expander, then there is excellent routing protocol by [Lenzen](https://arxiv.org/pdf/1903.05956.pdf). Using this routing protocol and some more, there is
* an algorithm for $(2 + \epsilon)$-approximation for **unweighted** APSP in $O(\log^2 n/\epsilon)$ rounds in undirected graph. And
* an algorithm for $(3 + \epsilon)$-approximation for **weighted** APSP in $O(\log^{O(1)} n/\epsilon)$ rounds in undirected graph. See [CDKL19](https://arxiv.org/pdf/1903.05956.pdf).
* When the graph has high min-degree, then also we can come up with a hard graph which given $\Omega(n)$ lower bound on congestion for computing reachability.

==**Question.** Can we show a $o(n)$ time algorithm for $(2 + \epsilon)$-approx unweighted APSP in graphs with high min-cut? Note that this is a stronger guarantee than high min-degree.==

**Follow-up question.** Can we show a good routing algorithm (say $o(n)$) for graphs with high min-cut?

**Comment.** This question needs clarification. How many messages a vertex $v$ needs to send/receive? Is it $deg(v)$?

## What is known?

### Tree-packing

**Spanning tree packing:** We have a collection of $\lambda$ many edge-disjoint spanning trees.

**Fractional spanning tree packing:** We have a collection of $\lambda$ many spanning trees such that
(i) Each tree $T$ has a weight $w_T \in [0,1]$ associated with it, and
(ii) For every edge $e$, $\sum_{T: e \in T} w_T \leq 1$.

[CHK](http://people.csail.mit.edu/ghaffari/papers/ConnectivityDecomp.pdf) shows:
* Any undirected graph with edge connectivity $\lambda$ can be decomposed into fractionally edge-disjoint weighted spanning trees with total weight $\approx \frac \lambda 2(1- \epsilon)$ in $\tilde O(D + \sqrt{n \lambda})$ time. ==What is $\epsilon$?==
* Any undirected graph with edge connectivity $\lambda$ can be decomposed into $\Omega(\lambda/\log n)$ many edge-disjoint weighted spanning trees in $\tilde O(D + \sqrt{n \lambda})$ time.
* There is a lower bound of $\Omega(D + \sqrt \frac n \lambda)$ of these decomposition algorithm, proven in the framework of Das-Sharma et al.

### 2-party congestion lower bound
* Consider all-pair reachability. Alice can compute a spanning forest of the edges which are exclusively her input, and send the spanning forest across to Bob. This gives congestion $\approx \frac n \lambda$.
* Consider APSP. In this case, Alice can compute a spanner instead. Using [Baswana, Sen](https://link.springer.com/chapter/10.1007%2F3-540-45061-0_32), Alice can send a $(1+\delta)$-spanner in congestion $n^{1 + \frac 2 {2+\delta}}/\lambda$.

==**Question.** Can we solve constant approx APSP in $o(n)$ time in graphs with high min-cut using spanners?==

**Comment.** So far we have two possible tools: (1) Better routing in CONGEST and using framework of CDKL19, and (2) Spanners.

### Low-congestion shortcuts

Check [this](https://hackmd.io/@t0_7Ars1RUqERlhD2KGiCQ/B1hrIGWbB/edit) note.

## Possible approach

We want something of the following type:
* We should be able to pack edge disjoint spanning forests $F_1, \cdots, F_k$ (where $k = n^{0.1}$ say) such that
* Each $F_i$ has small diameter.

In this case, the graph can compute a spanner in a distributed fashion where each vertex knows the local information of that spanner. The vertices then broadcast this local information over this graph by using $F_i$'s.

**Question.** If $G$ is a regular expander with high min-degree (which implies high min-cut for an expander) then how well can we broadcast messages in $G$?

**Claim**. For a degree $k$ expander $G$ on $n$ vertices, any $\tilde O(k)$-bit message can be broadcasted from a node in $poly \log n$ round.

There are a few ways of showing it.
#### Broadcast using GKS as black-box

This is the most trivial and straight-forward way of showing it. Recall the result of [GKS](https://groups.csail.mit.edu/tds/papers/Ghaffari/podc117.pdf).

**Theorem (GKS).** For an expander $G$, if each node is the source and destination of at most $deg(v)$ messages, there is a randomized distributed algorithm that delivers all messages in time $\tilde O(1)$.

* The broadcast algorithm starts from the root.
* In round $i$, let us assume that $2^i$ many vertices know the full message. These vertices choose another set of $2^i$ many vertices, and routes the message to all of these vertices. At the end of round $i$, a total of $2^{i+1}$ many vertices know the full message.
* This can go on for at most $\log n$ rounds. So the total round complexity is $poly \log n$.

#### Looking into Ghaffari's routing algorithm (Fat binary tree)

## Expander decomposition

See [this](https://hackmd.io/@sagnik/SJ2HZu3Zr/) note.

The general direction where we improve is the following tree packing theorem by [Nash-Williams](http://home.zcu.cz/~kaisert/papers/spanning-trees.pdf).

**Theorem (NW).** A graph $G$ contains $\lambda$ pairwise edge-disjoint spanning trees iff for any partition ${\cal P}$ of $V$, the contracted graph $G / {\cal P}$ has at least $\lambda (|{\cal P}|-1)$ edges.

Consider any graph $G$ with connectivity $\lambda$. For any $P \in {\cal P}$, $\partial(P) \geq \lambda$. This implies the following observation.

**Observation.** A graph $G$ with edge connectivity $\lambda$ has $\lambda |{\cal P}|/2$ edges in $G/ {\cal P}$.

Note that these spanning trees can have diameter as large as $n$. We will modify this in two respects:
* We will do away with the requirements that we need to pack tree. We will pack spanning subgraph. ==*We can make this spanning subgraphs to be spanning trees with similar diameter by using BFS trees.*==
* In doing so, we will achieve a shorter diameter $\approx n/\lambda$ for each of these spanning subgraph.

**Main theorem.** Given a graph $G$ on $n$ vertices with connectivity $\lambda$., it contains $\kappa$ many pair-wise edge-disjoint spanning trees with diameter $O(n/\kappa)$ where $\kappa = \lambda/n^{O(1/c)}$ for any $c = o(\log n)$.

*The converse is trivial:* Consider any cut. As each $G[E_i]$ is connected, each $E_i$ contributes at least 1 edge in that cut. Hence the size of the cut is at least $\lambda$.

$(\Rightarrow)$ We will use the following lemma.

**Lemma 1.** For any $c = o(\log n)$, given a graph $G$ on $n$ vertices with min degree $\lambda$, the vertex set $V$ can be partitioned into $V = K \cup J$ such that:
* $K$ is a union of $K_1, \cdots, K_t, t = n^{1 + O(1/c)}/\lambda$ where $G\{K_i\}$ is an expander with degree $\Omega(\lambda/n^{O(1/c)})$ and $O(\log^c n)$ mixing time,
* Each $v \in J$ has at least $\tilde \Omega(\lambda/n^{O(1/c)})$ many edge disjoint path (with the only common vertex being $v$) of length $\log n$ connecting $v$ to $K$.

We also use the following lemma about sparse expander packing.

**Lemma 2.** Given any expander $X$ with min degree $d$ and conductance $\Phi$, there is a partition of the edge set of $K$ into $O(d)$ many parts $\{X_1, \cdots, X_\ell\}$ such that
* $X_i$ is connected, and
* $\Phi(X_i) \geq (1 - \epsilon_d)\Phi$,

where $\epsilon_d$ is a constant dependent on $d$.

Given these two lemmas, this is how the proof goes.
* First, use Lemma 1 to decompose $G$ into expanders $K_1, \cdots, K_t$ and $J^{reg}$ where $t = n^{1 + O(1/c)}/\lambda$.
* Use Lemma 2 to decompose each $K_i$ into sparse expanders $K_i^1, \cdots, K_i^\kappa$ where $\kappa = n/t =\lambda/n^{O(1/c)}$.
* For each $v \in J^{reg}$, denote the paths associated with $v$ as $P_v^1, \cdots, P_v^\kappa$.
* Now, collect, for each $j \in [\kappa]$, $\{\{K_i^j\}_i, \{P_v^j\}_{v \in J}\}$ and call it $G^j$.
* Once this is done, we still have to connect each $G^j$' such that they stay pair-wise edge disjoint. To this end, we use Nash-Williams:
* Identify each vertex of $J^{reg}$ with the expander that it has a short path to.
* Contract each expander with all vertices in $J^{reg}$ who identify with that expander.
* At this point, we have a contracted graph $G^{cont}$ on $t$ many vertices with connectivity $\lambda$. This means, any partition $\cal P$ of $G^{cont}$ has $\lambda |{\cal P}|/2$ many edges. This, by Nash-Williams, implies that there are $\lambda/2$ many pairwise edge-disjoint spanning trees in $G^{cont}$. Pick any $\kappa$ of them, and name them $T_1, \cdots, T_\kappa$.
* Update $G^j$ by $G^j \cup T_j$.
* $G^1, \cdots, G^\kappa$ constitute the partition of $E$.

### Proof of Lemma 1

We use the following theorem from [SW19](https://arxiv.org/pdf/1812.08958.pdf).

**Theorem.** Given a graph $G$ on $n$ vertices and $m$ edges and a parameter $\phi$, there is a partition of $V$ in $K_1, \cdots, K_t$ such that
* $\Phi(K_i) \geq \phi$ and $\Phi(\{K_i\}) \geq \phi$,
* $\sum_i \partial(K_i) = O(\phi m \log^3 n)$.

Set $\phi = 1/(\log n)^c$ where we set $c$ later. The number of edges outside $K$ is $O(m/\log^{c-3} n)$.

**Observation.** Following the expander decomposition, the degree of each vertex inside $K_i$ is either 0 or at least $\phi \lambda$.

Consider any vertex $v$ inside the expander $K_i$ with non-zero degree. We have $\Phi(\{v\}) \geq \phi$ which means the number of neighbors of $v$ inside $K_i$ is $\phi$ times the degree of $v$.

We will also use the `Proc-deg-pruning` subroutine from [CK19](https://arxiv.org/pdf/1905.11512.pdf) which is similar to trimming.
> * Given a graph $H$ and a degree bound $d$,
> * $J^{core}$ is the set of vertices which has more than $d$ neighbors in $J^{core}$ (*core set*), rest of the vertices are in $J^{reg}$ (*regular set*).
> * This is achieved by pruning vertices from $J^{core}$ (which is initially $V(H)$) which has fewer than $d$ vertices in $J^{core}$ and putting them in $J^{reg}$.

The following lemma is useful from CK19.

**Lemma 3.** Let $H$ be a simple graph containing at most $n$ vertices and let $h$ be the min-degree of $H$. Let $(A,B)$ be any partition of vertices of $H$. Suppose we apply `Proc-deg-pruning`($H[B], \tau$) for any $\tau \leq h/(32 \log n)$. Then,
* The set $J^{reg}$ can be partitioned into $\ell = O(\log n)$ many layers $L_1, \cdots, L_\ell$,
* For any $i$, $|L_i| < |L_{i-1}|/2$,
* Any vertex $v \in L_i$ has at least $h/(2 \log n)$ neighbors of $v$ belongs to $L_{i-1}$.

**Corollary.** Every vertex $v \in J^{reg}$, there is a set ${\cal P}(v)$ of at least $h/(2\log n)$ paths in $H[A \cup J^{reg}]$, connecting $v$ to $A$, such that:
* The length of each path is at most $\log n$,
* The paths are completely disjoint except for sharing $v$.

We follow the iterative process:
* $J^{core} = V, h = \lambda$. (Initialization)
* Until $J^{core} = \emptyset$, do
* Apply Expander decomposition on $J^{core}$. Let $K = \bigcup K_i$ is the vertices covered by non-trivial expanders.
* Apply `Proc-deg-pruning`$(G[V - K], h/(32 log n))$.
* Update $J^{core}, J^{reg}$ and $h = h/(32 \log n)$.

We first bound the number of iterations of this algorithm.

**Claim.** The number of iterations is at most $O(\log n/(c \log \log n))$.

*Proof*. Every time we apply expander decomposition, the number of edges connection the expanders drops by a factor $\approx 1/\log^c n$. The total number of edges to start with was $m \leq n^2$. Hence the number of iterations possible is $O(\log n/(c \log \log n))$.

**Claim.** The number of expanders in the end is $n^{1 + O(1/c)}/\lambda$.

*Proof.* The degree bound, $h$, drops by a factor $(32 \log n)$ in each iterations. Using the bound on the number of iterations, $h \geq \lambda/n^{O(1/c)}$. Hence, each expander is of size at least $\lambda/n^{O(1/c)}$ which implies that the number of expanders is at most $n^{1 + O(1/c)}/\lambda$.

**Observation.** For every $v \in J^{reg}$, the size of ${\cal P}(v)$ is at least $\lambda/n^{O(1/c)}$.

### Proof of Lemma 2

**Lemma 2.** Given any expander $X$ with min degree $d$ and conductance $\Phi$, there is a partition of the edge set of $K$ into $O(d)$ many parts $\{X_1, \cdots, X_\ell\}$ such that
* $X_i$ is connected, and
* $\Phi(X_i) \geq (1 - \epsilon_d)\Phi$,

where $\epsilon_d$ is a constant dependent on $d$.

#### Spectral expander packing

**Lemma.** Consider an expander $G$ with min-degree $\lambda$ and conductance $\Phi(G)$. If we sample every edge with probability $1/\lambda$, then the sampled graph $G'$ is an expander with conductance $\Phi(G') \in \Phi(G)(1 \pm \epsilon)$ for any $\epsilon >0$ with high probability.

*Proof sketch.* Consider any cut $S, T$ of $G$ with $S$ being the smaller side. The conductance of this cut is $\Phi(S,G) = \frac{E_G(S,T)}{vol_G(S)}$. Now, for $G'$, $vol_{G'}(S) = vol_G(S)/\lambda$ on expectation. Similarly, $E_{G'}(S,T) = E_G(S,T)/\lambda$ on expectation.

First, we show that, for every $S$, $vol_{G'}(S) = vol_G(S)(1 + \delta_1)/\lambda$ with high probability. This can be achieved by Chernoff bound, which gives us the following: $\Pr[vol_{G'}(S) > vol_G(S)(1 + \delta_1)/\lambda] < \exp(-\delta_1^2 vol_G(S)/(2\lambda))$. The number of $S$ such that $vol_G(S) = k$ is at most ${n \choose k/\lambda}$. Call this set of $S$ as ${\cal S}_k$. So, by union bound, $\Pr[\exists S \in {\cal S}_k, vol_{G'}(S) > vol_G(S)(1 + \delta_1)/\lambda] < {n \choose k/\lambda}\exp(-\delta_1^2 k/(2\lambda)) < 1/n^5$. Now doing union bound over $k$, we get $vol_{G'}(S) > vol_G(S)(1 + \delta_1)/\lambda$ for all $S$ with probability $1 - 1/n^3$.

Second, we use the theorem from [ST11] who shows that $G'$ is a $(1 + \delta_2)/\lambda$-spectral sparsifier with probability at least $1 - 1/n^3$. As cut sparsifier is a special case of being a spectral sparsifier, we have that $E_{G'}(S,T) = E_G(S,T)(1 + \delta_2)/\lambda$ with that much probability.

**Corollary.** For any $\epsilon >0$, any expander $G$ with min-degree $\lambda$ and conductance $\Phi(G)$ can be partitioned into $\lambda$ many edge disjoint sparse expanders $G_1, \cdots, G_\lambda$ such that each such $G_i$ has conductance $\Phi(G_i) \in \Phi(G)(1 \pm \epsilon)$ with high probability.

<!--
* Get $\lambda$ down to logarithmic by random sampling.
* First pack MSTs with shortcuts. Each tree will take time $D \log n$. So total time $\lambda D$.
* -->