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)$