[TOC]

# Max-flow (Min-st-cut)

**Goal.** To avoid proving lower bound via bipartite matching (which is known to be hard). So
* Find an instance where the hardness is concentrated at other places.
* Prove lower bound for that hardness.

## Connection with matching

### Max-flow > Bipartite matching

This is the standard reduction.
> Given a maximum bipartite matching instance, construct a max-flow instance with unit capacity.

 :arrow_right: 

:point_right: The arcs have unit capacity. We can generalize it by considering $b$-matching

### Max-flow > Bipartite $b$-matching

In this case, the edges of the form $(s,u)$ has capacity $b(u)$.

### Bipartite $b$-matching > Max-flow

This reduction is in [this](https://drive.google.com/open?id=1V4OMGStdHQjce4lzZf8rgx2otNM3tece) paper by Madry.

:point_right: **Note.** The number of vertices in the $b$-matching instance is $n' = m + n$ where $m$ is the number of edges and $n$ is the number of vertices in the max-flow instance. So a high lower bound for max-flow (as high as $\Omega(m)$ will yield a lower bound of $\Omega(n')$ for $b$-matching.)

### $\Omega(n)$ lower bound for sparse $b$-matching

Essentially we can prove a $\Omega(n)$ lower bound for normal matching ($b = \bar 1$).

==Hence there is no hope to bypass the hardness of max-flow via $b$-matching unless there is a better reduction.==

---

## Query complexity of max-flow

### Trivial $\Omega(n)$ lower bound

### $\omega(n)$ lower bound: Attempt 1

Let's try to prove $\Omega(n^{1 + \delta})$ lower bound.

---

**Structural theorem.** If $s$ and $t$ are disconnected in the residual graph w.r.t. a flow, then the flow is a max-flow.

## Algorithm schema - 1

==Thse algorithms maintain all flow conservation constraints as invariants, and the goal is to achieve a residual graph where $s$ and $t$ are disconnected.==

### Edmond-Karp
*

### Dinic

* Consider a layered graph based on the distance from $s$.
* Admissible arcs are arcs going from $L_i$ to $L_{i+1}$.
* Admissible path is a path made of admissible arcs.

**Blocking flow.** A flow that saturates at least one arc in every admissible path from $s$ to $t$.

==Max-flow is a blocking flow, but not all blocking flows are max-flow.==

The algorithm is as follows:
- Find a blocking flow.
- Augment the current flow with the blocking flow.
- Repeat.

One only have to repeat $n$ times.

**How to find a blocking flow?** Use DFS in the following way:
1. ADVANCE: Take an admissible edge in the forward direction.
2. RETREAT: If there is no outgoing admissible edge at the current vertex, go back along the edge we came from, and delete it.

**2-party implementation**
1. *Finding admissible edges:* Alice and Bob needs to construct a layered graph. This needs an implementation of BFS.
2. *Finding a blocking flow:* This needs implementation of DFS.

Both BFS and DFS can be implemented in $\tilde O(n)$ communication in a 2-party model.

**Special case**
* In a graph arising from bipartite matching problem, the number of phases is bounded by $O(\sqrt n)$. CC = $\tilde O(n \sqrt n)$.
* In a graph with unit capacity, the number of phases is bounded by $\min\{\sqrt m, n^{2/3}\}$. CC = $\tilde O(n^{5/3})$ for dense graphs.

## Algorithm schema - 2

==These algorithms maintains that $s$ and $t$ are disconnected in the residual graph as invariant. The goal is to come up with a flow which satisfies the flow conservation constraints.==

### Push and relabel/Preflow-push

* Maintain a pre-flow and push excess flow from a vertex to the neighboring vertices.
* Maintain labeling to avoid circular movement of excess flow.
* End when preflow=flow. Because $s$ and $t$ are still disconnedted in this step, this is a max-flow.

---

## Bipartite matching

Unweighted case: CC = $O(n \sqrt n)$ by blocking flow. Also by Madry.

Weighted case: CC = $\tilde O(n \cdot \min\{n^{2/3}, \sqrt m\})$ by binary blocking flow. See [this](http://dimacs.rutgers.edu/archive/Workshops/Tarjan/materials/talk-slides/goldberg.pdf) talk for details.

This is also for max-flow. Note that when $\sqrt m \leq n^{2/3}$, then it is cheaper to send the edges to Bob. As we are only interested in dense graphs, the more interesting regime is when $\sqrt m \cdot n \leq m$, i.e., $m \geq n^2$.

**Conjecture.**

# Connections between graph problems


digraph  {

                nodesep=1.0 // increases the separation between nodes
                overlap = true

                node [color=Red,shape=box] //All nodes will this shape and colour
                edge [color=Blue, style=bold] //All the lines look like this
                SCC -> {Reachability} [label="(1)"]
                st_Reachability -> Reachability
                st_Reachability -> SCC
                Reachability -> {Shortest_path}
                Reachability -> Shortcut [style=dotted]
                Shortcut -> Reachability [label="(7)"]
                Top_ordering -> Reachability [style=dotted, label="Open (6)"]
                Shortest_path -> {Hopset}
                Shortest_path -> Top_ordering [style=dotted, label="Open (8)"]
                {Hopset} -> Spanner 
                Shortcut -> {Hopset}
                Shortest_path -> Mincost_flow
                Mincost_flow -> Mincost_max_flow
                Mincost_flow ->"b matching" [label="CohenMSV", color=Green]
                Max_flow -> "b matching" [ label = "Madry13", color=Green]
                Max_flow -> Min_st_cut [label="Strong dual"]
                Min_st_cut -> Max_flow
                "Bipart b matching" -> Max_flow [label="(4)"]
                Bipart_matching ->"Bipart b matching"
                Reachability -> Bipart_matching [label="(3)"]
                Bipart_matching ->Reachability [label="(5)"]
                Bipart_matching -> Vertex_cover [label="Strong dual"]
                Vertex_cover -> Bipart_matching
                Bipart_matching -> Matroid_int
                Min_st_cut -> SFM
                Max_flow -> Mincost_max_flow
                Dir_mincut -> Matroid_int [label="check"]
                {rank=same;Bipart_matching Vertex_cover}
                {rank=same;Max_flow Min_st_cut}
}

digraph  {

                nodesep=1.0 // increases the separation between nodes
                overlap = true

                node [color=Red,shape=box] //All nodes will this shape and colour
                edge [color=Blue, style=bold] //All the lines look like this
                Arborescense -> Matroid_int
                Orientation -> Matroid_int
                Color_Spanning_tree -> Matroid_int
                Dir_mincut -> Matroid_int [label="check"]
}
                

#### (3): *Reachability $\rightarrow$ Bipartite matching:*

**Claim.** Reachability reduces to perfect bipartite matching.

Given an instance of reachability (multi-source-multi-sink), it can be converted to an instance of perfect bipartite matching as follows:

Given a graph $G$ with source nodes $s_1, \cdots, s_k$ and sink nodes $t_1, \cdots, t_k$, we convert it to a bipartite graph $G' = (A,B, E')$ in the following way:
- For each vertex v which is not a source or sink node, put $v_L$ in $A$ and $v_R$ in $B$ and connect them by an edge in $E'$. (blue edge)
- Put $s_1, \cdots, s_k$ in $A$, and $t_1, \cdots, t_k$ in $B$.
- For every edge $(u,v) \in E$, put an edge $(u_L, v_R) \in E'$. (red edge)

**Claim.** If there is a perfect matching, then every source can reach a sink.

*Proof.* Consider any source $s$. Follow the path from $s$ alternating red and blue edge. As this is a perfect matching, this path must be an augmenting path with respect to the blue matching. So it ends in a sink node.

The corresponding path in $G$ will send the source to the sink.

#### (1) SCC $\rightarrow$ Reachability

Belloch et al. Also see email "Upper bound: Distributed strongly connected components".

#### (2) $st$-Reachability $\rightarrow$ SCC

- Add an arc $(s,t)$.
- Run SCC algorithm and check if $s$ and $t$ are in the same connected component.

#### (5) Bipartite matching $\rightarrow$ Reachability

If we have an algorithm for reachability with complexity $T(d)$ where $d$ is the depth up to which reachability is computed, then we have the following:

**Fact.** If $s$ is the size of maximum matching, and $i$ is the size of any matching, then there is an augmenting path of length at most $\frac s {s - i}$.

- The complexity is $T(n/n) + T(n/n-1) + \cdots + T(n)$.
- If $T(d)$ is linear in $d$, then the complexity is $T(n) \cdot HP(n) \approx T(n) \log n$.

#### (4) Bipartite $b$ matching $\rightarrow$ Max-flow

See [above](#Max-flow-gt-Bipartite-b-matching).

#### (7) Shortcuts $\rightarrow$ Reachability

The ideas are from [this](https://arxiv.org/pdf/1711.01700.pdf) paper of Jeremy Fineman.