Question

There are many common variations of the maximum flow problem. Here are four of them.

(a) There are many sources and many sinks, and we wish to maximize the total flow from all sources to all sinks.

(b) Each vertex also has a capacity on the maximum flow that can enter it.

(c) Each edge has not only a capacity, but also a lower bound on the flow it must carry.

(d) The outgoing flow from each node u is not the same as the incoming flow, but is smaller by a factor of $\left(1-{\in }_U\right)$, whererole="math" localid="1659789093525" ${\mathbf{\in }}_{\mathbf{u}}$ is a loss coefficient associated with node u.

Each of these can be solved efficiently. Show this by reducing (a) and (b) to the original max-flow problem, and reducing (c) and (d) to linear programming.

Short answer

(a) and (b) can be reduced to original max-flow. Also, (c) and (d) will be reduced to linear programming.

Step-by-step solution

Step-1:Solve the variation of maximum flow in subpart (a)

(a)

Consider that, $G\left(V,E\right)$ is a graph where V and E are set of vertices and edges respectively of graph G.S is Source nose or starting node. T is Terminating or sink node. I is Internal nodes which not include S or T.

The reduced graph from multi-source, multi-sink flow to single-source, single-sink flow will be $G\text{'}\left(V\text{'},E\text{'}\right)$.

Here, $V\text{'}=\left\{s,t\right\}+VandE\text{'}=\left\{\left(s,a,\infty \right)la\in S\right\}+E+\left\{\left(b,t,\infty \right)lb\in T\right\}$.

Therefore, the given variation can be solved for Maximum flow s-t on graph G'.

Step-2:Solve the variation of maximum flow in subpart (b)

(b)

Let there be a vertex $v\in V$ and C_v be the capacity(weight) of the vertex v.

Reduce from node-capacity maximum flow to simple max flow will be:

Consider, $G\text{'}\left(V\text{'},E\text{'}\right)withV\text{'}=\left\{a_{in}\overline{)a\in V}\right\}+\left\{a_{out}\overline{)a\in V}\right\}andE\text{'}=\left\{\left(a_{in},a_{out},C\overline{)a\in E}\right)\right\}+\left\{\left(a_{out},B_{in},C_{\left(a,b\right)}\overline{)\left(a,b\right)\in E}\right)\right\}$,

Therefore, The given variation can be solved for maximum flow on s_in- t_out graph G'.

Step-3:Solve the variation of maximum flow in subpart (c)

(c)

Consider that $i:N\to e$, be the bijective mapping(means every element has being matched) between the edge of the graph and set of natural numbers. C_i,Capacity of edge i, L_i, lower bound of i, and F, Flow along the edge i .

Maximize the sum of f_{i ,} i.e.,

Maximize:$\sum _{\left(ie\left(s,v\right)\right)}{f}_i$

Constraints:

$f_i\le C_i$for all$i\in E$ (Capacities)

$f_i\le L_i$for all$i\in E$ (Lower Bounds)

$\sum _{iintov}{f}_i-\sum _{joutofv}{f}_j$for all$v\in V-\left\{s,t\right\}$ (Conservation)

Therefore, The given variation can be solved for maximum flow.

Step-4: Solve the variation of maximum flow in subpart (d)

(d)

Consider that, e_v be the loss coefficient along each of the node, such that$out-flow=\left(1-e_v\right)inflow\left(v\right)$ for all internal nodes l.

Maximize the sum of all values of f_i

Maximize:$\sum _{\left(i\in \left(s,v\right)\right)}{f}_i$

Constraints:

localid="1659791095962" $f_i\le C_i$for all$i\in E$ (Capacities)

$\sum _{iintov}\left(1-e_i\right)f_i-\sum _{joutofv}{f}_j$for all$v\in V-\left\{s,t\right\}$ (Lossy Conservation).

Therefore, The given variation can be solved for maximum flow.