# Max-flow lower bound

* Given a function $\hat f : E \to {\mathbb R}$, it can be checked cheaply by Alice and Bob if $\hat f$ is a flow:
* Flow-conservation constraints: Alice can send $\Delta_A(v)= \sum_{e \in \delta_A^-(v)}f(e) - \sum_{e \in \delta_A^+(v)}f(e)$ to Bob for all $v \in V$. This needs $O(n \log n)$ communication.
* Capacity constraints: This is local computation.

* Alice gets a flow $f_A$ and Bob gets a flow $f_B$. Then $f_A \cup f_B$ is a valid flow. What goes wrong if Alice computes the max-flow w.r.t. $E_A$, Bob computes the max-flow w.r.t. $E_B$ and they take their union?
* $E_A$ does not have an $s-t$ path, and neither does $E_B$.
* Consider a layered graph with vertex layers $V_1, \cdot V_k$ where each $V_i$ has $\ell$ nodes and $\ell \times k = n$. There is no edge inside $V_i$. All edges are between two consecutive layers and directed from smaller labeled layer to the bigger one. Alice holds odd layer edges and Bob holds even layer edges.
* ~~Interactive rounds: In round $i$:~~
* ~~If $i$ is odd, then Alice reports how much flow can be routed to each vertex in $V_{i+1}$ given the incoming flow in $V_i$.~~
* ~~If $i$ is even, Bob does the same.~~
* ~~Total communication = $O(n \log n)$. Cannot prove high lower bound.~~
* This is not true.

* Single source max flow > directed min-cut
* Pick a random node, compute single souce max flow form this node.
* Is there a connection between directed min-cut and $st$-max-flow?

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] 
"Directed min-cut" -> "single source flow" [label="[Danupon-Sorrachai]"]
"st-Max flow" -> "single source flow"
"single source flow" -> "All pair flow"
"Directed min-cut" -> "st-Max flow" [label="?"]
"st-Max flow" -> "Directed min-cut"
{rank=same;"Directed min-cut" "st-Max flow"}
}