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