Applications of Network Flow

Circulation with Demands

Given:
- Graph $G(V,E)$
- Capacities on the edges
- Demands for each vertex ${d_v}$ such that
    - $d_v > 0 \implies$ Net flow into vertex (Source)
    - $d_v < 0 \implies$ Net flow out of vertex (Sink)
    - $d_v = 0 \implies$ Inflow equals outflow (Normal Node)

Definition: Circulation
Circulation is a function $f: E \rightarrow \mathbb{R}^+$ which satisfies the following
- Bounded by capacity: $f(e) \leq c(e)$
- Conservation condition: $f^{in}(v) - f^{out}(v) = d_v$

Lemma: Necessary condition for Feasible circulation $\rightarrow \sum_v d_v = 0$ 
Proof:
\begin{align}
\sum_v d_v & = \sum_v f^{in}(v) - f^{out}(v) \\
                  & = \sum_v f^{in}(v) - \sum_v f^{out}(v) \\
                  & = 0
\end{align}
Since flow on every edge appears twice once as inflow on a vertex and other time as outflow on the other vertex on that edge.
In other words, there is a feasible solution only if $D = \sum_{v>0}d_v = \sum_{v<0} {- d_v}$

Algorithm: Finding Circulation 
- Check necessity condition
- Connect all vertices with $d_v < 0$ to a super source via edges with capacity $-d_v$
- Connect all vertices with $d_v > 0$ to a super source via edges with capacity $d_v$
- On this flow network $H$, compute max-flow
- If flow value is $D$, then we have a valid circulation
- Else, circulation is infeasible

Correctness:
If there is a valid circulation in $G$, then in $H$ there is a $s-t$ max flow with value $D$ obtained by pushing full capacities from source to the vertices with negative demand.

Conversely, a max-flow with value $D$ in $H$ is possible only when full capacities of the subordinate sources are used which implies that both capacity constraint and conservation condition are maintained. Hence there is a valid circulation in $G$.

Circulation with Demands and Lower bounds

Given:
- Graph $G(V,E)$
- Capacities on the edges
- Demands for each vertex ${d_v}$
- Lower bound for each edge $\ni l(e) \leq c(e)$

Now, a valid circulation is one where $l(e) \leq f(e) \leq c(e)$.

Algorithm: Get rid of the lower bound somehow and then solve the circulation with demands
- Push a flow equal to the lower bound on each edge
- It satisfies the bounds
- Does not satisfy the conservation of flow
- Let $L_v = f^{in}(v) - f^{out}(v)$ be the residual demand
- Set the new $d'_v = d_v - L_v$ and reduce the capacities to $c'(e) = c(e) - l(e)$ to get new graph $G'$
- The lower bounds vanish
- Solve the circulation problem in $G'$
- Add the circulation to the lower bounds $f = f_0 + f'$

Correctness:
Want to show that $G$ has valid circulation with demands and lower bounds if and only if $G'$ has a valid circulation with demands.
First we show, $(f \text{ is valid } \implies f' \text{ is valid } )$
- $f(e) - l(e) \leq c(e) - l(e) \implies f'(e) \leq c'(e) \rightarrow$ hence bounded by capacity
- $\sum_{e \; into \; v } (f(e) - l(e)) - \sum_{e \; out \; of \; v} (f(e) - l(e)) = d_v - L_v \rightarrow$ hence flow is conserved

Now we show, $(f '\text{ is valid } \implies f \text{ is valid } )$
- Clearly $l(e) \leq f_0(e) + f'(e) \leq l(e) + c'(e) = c(e) \rightarrow $ hence satisfies the bounds
- $\sum_{e \; into \; v } (l(e) + f'(e)) - \sum_{e \; out \; of \; v} (l(e) + f'(e)) = L_v + (d_v - L_v) = d_v \rightarrow$ hence the flow is conserved

Hence proved.

Survey Design

Problem Statement:
Given:
- Set of consumers
- Set of products
- List of products that each consumer has consumed

Want:
- To ask questions to the consumer about a subset of the products that the consumer used
- $i^{th}$ consumer would answer only questions in the range $[c_i, c'_i]$
- For the $i^{th}$ product we want to ask question in the range $[p_i, p'_i]$

Question:
How to assign questions to the consumers so that we get required information about each product while keeping the consumers happy?

Algorithm:
- Form a Bipartite graph with consumers on one side and products on the other
- Connect the consumers with the products that they used by an edge with capacity $1$
- Connect the consumers to a source $S$ with edges of capacities with lower $(c_i)$ and upper $(c'_i)$ bound
- Connect the products to a sink $T$ with edges of capacities with lower $(p_i)$ and upper $(p'_i)$ bound
- We want to get a flow from $S$ to $T$
- But we only know how to compute a circulation
- So connect $T$ to $S$ by an edge of infinite capacity
- Demands on all the vertices including source and sink is 0
- Happily compute a circulation with lower bounds on this network

Time Complexity: 
- $n$ consumers
- $u$ products
- $m \leftarrow$ sum of the number of products used by the consumers
- $|E| = m$
- $|V| = n + u$
- $O(|V||E|^2) = O((n+u) m^2)$

Applications of Network Flow

Edge Disjoint Paths Problem

Given:
- Directed or undirected graph $G$
- Vertices $s$ and $t$
- Parameter k

Task: Compute $k$ edge disjoint paths from $s$ to $t$

Directed Graph

Lemma: Number of edge disjoint paths equals max flow
- Construct a network flow $H$ where all edges have capacity $1$
- Since capacities are integral, the max-flow would have either $0$ or $1$ unit of flow on each edge
- Such a flow is called $0/1$ flow
- $|f_H| = \text{number of edge disjoint paths in G}$

Proof: Unclear

Algorithm:
- Start walking from $s$ along an edge with flow $1$
- If reach $t$, then add the path to the set of edge disjoint paths
- Else if reached a vertex a second time (a cycle!), then remove the edges that form the cycle
- Since $|f| \leq |V|$, Ford-Fulkerson outputs the flow in $O(|V||E|)$ time
- Extracting the paths from the flow takes $O(|E|)$ time
- Hence edge disjoint paths can be found in $O(|V||E|)$ time

Lemma: Maximum number of edge disjoint paths equals the minimum number of edges whose removal separates s from t
Proof:
$U \leftarrow$  set of edge disjoint paths
$F \leftarrow$ set of removed edges such that $s$ and $t$ are disconnected
First show $|U| \leq |F|$
- $F$ must contain at least one edge from each path in $U$
- Hence $|U| \leq |F|$

Now,
- $S = \{v \in V | \exists \text{ path from } s \text{ to } t \text{ which does not use any edge in } F \}$
- $T = V \setminus S$
- $F$ defines a cut $(S,T)$
- Clearly $|F| \geq c(S,T)$
- Any edge in $F$ that is not in the cut can be discarded to get $F_{minimal}$
- $|F_{minimal}| = c(S,T)$
- The smallest such set has size, $|F^*| = $ min-cut in $G$
- By Max-Flow Min-Cut theorem $|F^*| = |f_{max}|$, i.e max-flow in $G$
- By previous lemma $|F^*| = $ number of edge disjoint paths

Undirected Graph

- Double every edge to give 2 directed edges

- Repeat the algorithm for directed case

- Again $f$ might push flow along both $(u\rightarrow v)$ and $(v\rightarrow u)$ 

- But this is a cycle!

- Remove cycle and get on with life