Editing Maximum flow problem (section)

==Application==

===Multi-source multi-sink maximum flow problem===
[[File:Multi-source multi-sink flow problem.svg|thumb|right|Fig. 4.1.1. Transformation of a multi-source multi-sink maximum flow problem into a single-source single-sink maximum flow problem]]
Given a network <math>N = (V, E)</math> with a set of sources <math>S = \{s_1, \ldots, s_n\}</math> and a set of sinks <math>T = \{t_1, \ldots, t_m\}</math> instead of only one source and one sink, we are to find the maximum flow across <math>N</math>. We can transform the multi-source multi-sink problem into a maximum flow problem by adding a ''consolidated source'' connecting to each vertex in <math>S</math> and a ''consolidated sink ''connected by each vertex in <math>T</math> (also known as ''supersource'' and ''supersink'') with infinite capacity on each edge (See Fig. 4.1.1.).

===Maximum cardinality bipartite matching===
[[File:Maximum bipartite matching to max flow.svg|thumb|right|Fig. 4.3.1. Transformation of a maximum bipartite matching problem into a maximum flow problem]]
Given a [[bipartite graph]] <math>G = (X \cup Y, E)</math>, we are to find a [[maximum cardinality matching]] in <math>G</math>, that is a matching that contains the largest possible number of edges. This problem can be transformed into a maximum flow problem by constructing a network <math>N = (X \cup Y \cup \{s,t\}, E')</math>, where
# <math>E'</math> contains the edges in <math>G</math> directed from <math>X</math> to <math>Y</math>.
# <math>(s,x) \in E'</math> for each <math>x \in X</math> and <math>(y,t) \in E'</math> for each <math>y \in Y</math>.
# <math>c(e) = 1</math> for each <math>e \in E'</math> (See Fig. 4.3.1).

Then the value of the maximum flow in <math>N</math> is equal to the size of the maximum matching in <math>G</math>, and a maximum cardinality matching can be found by taking those edges that have flow <math>1</math> in an integral max-flow.

===Minimum path cover in directed acyclic graph===
Given a [[directed acyclic graph]] <math>G = (V, E)</math>, we are to find the minimum number of [[Path (graph theory)|vertex-disjoint paths]] to cover each vertex in <math>V</math>. We can construct a bipartite graph <math>G' = (V_\textrm{out} \cup V_\textrm{in}, E')</math> from <math>G</math>, where
# <math>V_\textrm{out} = \{ v_\textrm{out} \mid v \in V \land v \text{ has outgoing edge(s)} \}</math>
# <math>V_\textrm{in} = \{ v_\textrm{in} \mid v \in V \land v \text{ has incoming edge(s)} \}</math>
# <math>E' = \{(u_\textrm{out}, v_\textrm{in}) \in V_{out} \times V_{in} \mid (u, v) \in E \}</math>.

Then it can be shown that <math>G'</math> has a matching <math>M</math> of size <math>m</math> if and only if <math>G</math> has a vertex-disjoint path cover <math>C</math> containing <math>m</math> edges and <math>n-m</math> paths, where <math>n</math> is the number of vertices in <math>G</math>. Therefore, the problem can be solved by finding the maximum cardinality matching in <math>G'</math> instead.

Assume we have found a matching <math>M</math> of <math>G'</math>, and constructed the cover <math>C</math> from it. Intuitively, if two vertices <math>u_\mathrm{out}, v_\mathrm{in}</math> are matched in <math>M</math>, then the edge <math>(u, v)</math> is contained in <math>C</math>. Clearly the number of edges in <math>C</math> is <math>m</math>. To see that <math>C</math> is vertex-disjoint, consider the following:
# Each vertex <math>v_\textrm{out}</math> in <math>G'</math> can either be ''non-matched'' in <math>M</math>, in which case there are no edges leaving <math>v</math> in <math>C</math>; or it can be ''matched'', in which case there is exactly one edge leaving <math>v</math> in <math>C</math>. In either case, no more than one edge leaves any vertex <math>v</math> in <math>C</math>.
# Similarly for each vertex <math>v_\textrm{in}</math> in <math>G'</math> – if it is matched, there is a single incoming edge into <math>v</math> in <math>C</math>; otherwise <math>v</math> has no incoming edges in <math>C</math>.
Thus no vertex has two incoming or two outgoing edges in <math>C</math>, which means all paths in <math>C</math> are vertex-disjoint.

To show that the cover <math>C</math> has size <math>n-m</math>, we start with an empty cover and build it incrementally. To add a vertex <math>u</math> to the cover, we can either add it to an existing path, or create a new path of length zero starting at that vertex. The former case is applicable whenever either <math>(u,v) \in E</math> and some path in the cover starts at <math>v</math>, or <math>(v,u) \in E</math> and some path ends at <math>v</math>. The latter case is always applicable. In the former case, the total number of edges in the cover is increased by 1 and the number of paths stays the same; in the latter case the number of paths is increased and the number of edges stays the same. It is now clear that after covering all <math>n</math> vertices, the sum of the number of paths and edges in the cover is <math>n</math>. Therefore, if the number of edges in the cover is <math>m</math>, the number of paths is <math>n-m</math>.

===Maximum flow with vertex capacities===
[[File:Node splitting.svg|thumb|right|Fig. 4.4.1. Transformation of a maximum flow problem with vertex capacities constraint into the original maximum flow problem by node splitting]]

Let <math>N = (V, E)</math> be a network. Suppose there is capacity at each node in addition to edge capacity, that is, a mapping <math>c: V\to \R^+,</math> such that the flow <math>f</math> has to satisfy not only the capacity constraint and the conservation of flows, but also the vertex capacity constraint

:<math> \sum_{i\in V} f_{iv} \le c(v) \qquad \forall v \in V \backslash \{s,t\}.</math>

In other words, the amount of flow passing through a vertex cannot exceed its capacity. To find the maximum flow across <math>N</math>, we can transform the problem into the maximum flow problem in the original sense by expanding <math>N</math>. First, each <math>v\in V</math> is replaced by <math>v_{\text{in}}</math> and <math>v_{\text{out}}</math>, where <math>v_{\text{in}}</math> is connected by edges going into <math>v</math> and <math>v_{\text{out}}</math> is connected to edges coming out from <math>v</math>, then assign capacity <math>c(v)</math> to the edge connecting <math>v_{\text{in}}</math> and <math>v_{\text{out}}</math> (see Fig. 4.4.1). In this expanded network, the vertex capacity constraint is removed and therefore the problem can be treated as the original maximum flow problem.

===Maximum number of paths from s to t===
Given a directed graph <math>G = (V, E)</math> and two vertices <math>s</math> and <math>t</math>, we are to find the maximum number of paths from <math>s</math> to <math>t</math>. This problem has several variants:

1. The paths must be edge-disjoint. This problem can be transformed to a maximum flow problem by constructing a network <math>N = (V, E)</math> from <math>G</math>, with <math>s</math> and <math>t</math> being the source and the sink of <math>N</math> respectively, and assigning each edge a capacity of <math>1</math>. In this network, the maximum flow is <math>k</math> iff there are <math>k</math> edge-disjoint paths.

2. The paths must be independent, i.e., vertex-disjoint (except for <math>s</math> and <math>t</math>). We can construct a network <math>N = (V, E)</math> from <math>G</math> with vertex capacities, where the capacities of all vertices and all edges are <math>1</math>. Then the value of the maximum flow is equal to the maximum number of independent paths from <math>s</math> to <math>t</math>.

3. In addition to the paths being edge-disjoint and/or vertex disjoint, the paths also have a length constraint: we count only paths whose length is exactly <math>k</math>, or at most <math>k</math>. Most variants of this problem are NP-complete, except for small values of <math>k</math>.<ref>{{Cite journal|last1=Itai|first1=A.|last2=Perl|first2=Y.|last3=Shiloach|first3=Y.|year=1982|title=The complexity of finding maximum disjoint paths with length constraints|journal=Networks|language=en|volume=12|issue=3|pages=277–286|doi=10.1002/net.3230120306|issn=1097-0037}}</ref>

=== Closure problem ===
{{Main|Closure problem}}
A '''closure''' of a directed graph is a set of vertices ''C'', such that no edges leave ''C''. The '''closure problem''' is the task of finding the maximum-weight or minimum-weight closure in a vertex-weighted directed graph. It may be solved in [[Time complexity|polynomial time]] using a reduction to the maximum flow problem.