# [Public Draft] Expander decomposition

For more information, watch the [survey by Saranurak](https://youtu.be/4tTdU08_YBo).

## 1. Statements

Below are the statements for the directed version. I only state the "edge version". For the "vertex version", see Fact 3.2 in [BGS20]. The undirected version is a special case of this, except that it can be computed deterministically in $m^{o(1)}$ time.

**Definitions**
* For any directed graph $G=(V, E)$ and $S\subseteq V$, $vol(S) := \sum_{u∈S} deg(u).$
* For any $S\subseteq V$ s.t. $vol(S)\leq vol(V\setminus S)$, we say that the cut $(S, V\setminus S)$ is $\phi$-sparse if $\min(\delta^{in}(S), \delta^{out}(S)) < \phi \cdot vol(S)$
* $\delta^{in}(S):=$ number of edges from $u\notin S$ to $v\in S$.
* $G$ is $\phi$-expander if it has no $\phi$-sparse cut. Note: A single vertex is an expander.

### 1.1 Existence
**Theorem 1 (existence):**
* INPUT: Given an $m$-edge, $n$-vertex directed unweighted graph $G = (V,E,w)$ and a parameter $\phi>0$,
* EXIST: An edge set $E_{Rem}\subseteq E$ such that
1. each SCCs of $G\setminus E_{rem}$ is a $\phi$-expander,
* i.e. for any SCC $G[V']$ of $G\setminus E_{rem}$ and any $S\subseteq V'$ s.t. $vol_{G[V']}(S)\leq vol_{G[V']}(V'\setminus S)$, we have $\min(\delta^{in}_{G[V']}(S), \delta^{out}_{G[V']}(S)) \geq \phi \cdot vol(S),$
2. $|E_{rem}|=O(\phi m\log(m)).$

**Proof sketch:**
* If there is a $\phi$-sparse cut $S$, say $\delta^{in}_{G}(S) < \phi \cdot vol(S),$ put $\delta^{in}_{G}(S)$ edges pointing from $V\setminus S$ to $S$ to $E_{rem}$.
* Charge the "cost" of putting these edges to $E_{rem}$ to edges incident to $S$.
* Each edge is charged $O(\phi)$ (since $\delta^{in}_{G}(S) < \phi \cdot vol(S)$).
* Everytime an edge is charged, the volume of its strongly connected component is halved.
* So, every edge is charged $O(\phi \log(m))$ cost, thus $|E_{rem}|=O(\phi m\log(m))$.

**Examples for the argument for both undirected and directed cases:**


*Remark: The same argument holds for weighted graphs by treating them as multigraphs.*

### 1.2 Algorithm

The result below is implicit in [BGS20]. For the undirected version, see [CGL+19,SW19].

**Theorem 2 (fast algorithm):** There is a randomized algorithm $ExDec(G,\phi)$ with the following guarantees:
* INPUT: Given an $m$-edge, $n$-vertex directed weighted graph $G = (V,E,w)$ and a parameter $\phi>0$,
* OUTPUT: An edge set $E_{Rem}\subseteq E$ such that, w.h.p.,
1. each SCCs of $G\setminus E_{rem}$ is a is a $\phi$-expander,
2. $|E_{rem}|<\phi mn^{o(1)}\log(m).$
* RUNTIME: $m^{1+o(1)}$.

*Remark:* The runtime of the above algorithm is based on the runtime of maxflow, which is currently $m^{1+o(1)}$.

### 1.3 Examples
From the [survey by Saranurak](https://youtu.be/4tTdU08_YBo):


## 2. Role in recent fast maxflow algorithm [CKL+22]

**Outerloop:** Continuous optimization
* Detail: Classic interior point method (but need to change the log-barrier to something similar).

**Innerloop:** 2 dynamic data structures
1. **j-tree via Low-Diameter Decomposition**
* Extend from, e.g., [CGH+20] but needs new tricks to work against an "adversary" created by the outer-loop
* Roughly, this is a collection of "trees" where every cut is approximately preserved in one of the trees. But, in each trees, $j$ nodes can form a subgraph (thus not a tree).
2. **Dynamic spanner via expander decomposition**
* Roughly, a spanner is a subgraph that approximately preserves distances
* Use (undirected, static) expander decomposition so the spanner has some additional properties
* For an idea how graph decomposition is related to spanner, see Question 3 [here](https://hackmd.io/4xFyeGkaQhiBr6j--RoDTQ).

## 3. Some other Applications

### 3.1 Undirected expander decomposition

The pictures below are copied/modified from the [survey by Saranurak](https://youtu.be/4tTdU08_YBo):

**Derandomizing static algorithms:**


* $\tilde O(m+n^{1.5})$-time bipartite matching and maxflow
* Used to list edges with "large” flow in $\tilde O(𝑛)$ time. Key ingredients: Dynamic Expander Decomposition + $\tilde O(n)$-time algorithm on expanders.
* Simple deterministic mincut on simple graphs

**Dynamic problems:** (Undirected) expander decomposition can be maintained under edge deletions/insertions. It leads to many fast dynamic graph algorithms.


**Distributed Algorithms:** Trianle and k-clique listing.


### 3.2 Directed expander decomposition

The only application of the directed version is dynamic problems related to shortest paths in [BGS20]. *Open:* Other applications of directed expander decomposition?

## References

[BGS20] Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak:
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing. FOCS 2020: 1123-1134

[CGH+20] Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, Thatchaphol Saranurak:
Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers. FOCS 2020: 1135-1146

[CGL+19] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak:
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. FOCS 2020

[CKL+22] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. FOCS 2022

[SW19] Thatchaphol Saranurak, Di Wang: Expander Decomposition and Pruning: Faster, Stronger, and Simpler. SODA 2019: 2616-2635