Combinatorics (Fall 2010)/Flow and matching

Flow and Cut

Flows

An instance of the maximum flow problem consists of:

• a directed graph [math]\displaystyle{ G(V,E) }[/math];
• two distinguished vertices [math]\displaystyle{ s }[/math] (the source) and [math]\displaystyle{ t }[/math] (the sink), where the in-degree of [math]\displaystyle{ s }[/math] and the out-degree of [math]\displaystyle{ t }[/math] are both 0;
• the capacity function [math]\displaystyle{ c:E\rightarrow\mathbb{R}^+ }[/math] which associates each directed edge [math]\displaystyle{ (u,v)\in E }[/math] a nonnegative real number [math]\displaystyle{ c_{uv} }[/math] called the capacity of the edge.

The quadruple [math]\displaystyle{ (G,c,s,t) }[/math] is called a flow network.

A function [math]\displaystyle{ f:E\rightarrow\mathbb{R}^+ }[/math] is called a flow (to be specific an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow) in the network [math]\displaystyle{ G(V,E) }[/math] if it satisfies:

• Capacity constraint: [math]\displaystyle{ f_{uv}\le c_{uv} }[/math] for all [math]\displaystyle{ (u,v)\in E }[/math].
• Conservation constraint: [math]\displaystyle{ \sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw} }[/math] for all [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math].

The value of the flow [math]\displaystyle{ f }[/math] is [math]\displaystyle{ \sum_{v:(s,v)\in E}f_{sv} }[/math].

Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

The maximum flow problem can be described as the following linear program.

[math]\displaystyle{ \begin{align} \text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\ \begin{align} \text{subject to} \\ \\ \\ \\ \end{align} \quad & \begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\ \sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\ f_{uv}&\ge 0 &\quad& \forall (u,v)\in E \end{align} \end{align} }[/math]

Cuts

Definition

Let [math]\displaystyle{ (G(V,E),c,s,t) }[/math] be a flow network. Let [math]\displaystyle{ S\subset V }[/math]. We call [math]\displaystyle{ (S,\bar{S}) }[/math] an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut if [math]\displaystyle{ s\in S }[/math] and [math]\displaystyle{ t\not\in S }[/math]. The value of the cut (also called the capacity of the cut) is defined as [math]\displaystyle{ \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math].

A fundamental fact in flow theory is that cuts always upper bound flows.

Lemma

Let [math]\displaystyle{ (G(V,E),c,s,t) }[/math] be a flow network. Let [math]\displaystyle{ f }[/math] be an arbitrary flow in [math]\displaystyle{ G }[/math], and let [math]\displaystyle{ (S,\bar{S}) }[/math] be an arbitrary [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut. Then [math]\displaystyle{ \sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math], that is, the value of any flow is no greater than the value of any cut.

Proof. By the definition of [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut, [math]\displaystyle{ s\in S }[/math] and [math]\displaystyle{ t\not\in S }[/math]. Due to the conservation of flow, [math]\displaystyle{ \sum_{u\in S}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}+\sum_{u\in S\setminus\{s\}}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}\,. }[/math] On the other hand, summing flow over edges, [math]\displaystyle{ \sum_{v\in S}\left(\sum_{u:(u,v)\in E}f_{uv}-\sum_{u:(v,u)\in E}f_{vu}\right)=\sum_{u\in S,v\in S\atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\,. }[/math] Therefore, [math]\displaystyle{ \sum_{v:(s,v)\in E}f_{sv}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,, }[/math] [math]\displaystyle{ \square }[/math]

Augmenting paths

Definition (Augmenting path)

Let [math]\displaystyle{ f }[/math] be a flow in [math]\displaystyle{ G }[/math]. An augmenting path to [math]\displaystyle{ u_k }[/math] is a sequence of distinct vertices [math]\displaystyle{ P=(u_0,u_1,\cdots, u_k) }[/math], such that [math]\displaystyle{ u_0=s\, }[/math]; and each pair of consecutive vertices [math]\displaystyle{ u_{i}u_{i+1}\, }[/math] in [math]\displaystyle{ P }[/math] corresponds to either a forward edge [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math] or a reverse edge [math]\displaystyle{ (u_{i+1},u_{i})\in E }[/math], and [math]\displaystyle{ f(u_i,u_{i+1})\lt c(u_i,u_{i+1})\, }[/math] when [math]\displaystyle{ u_{i}u_{i+1}\, }[/math] corresponds to a forward edge [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math], and [math]\displaystyle{ f(u_{i+1},u_i)\gt 0\, }[/math] when [math]\displaystyle{ u_{i}u_{i+1}\, }[/math] corresponds to a reverse edge [math]\displaystyle{ (u_{i+1},u_{i})\in E }[/math]. If [math]\displaystyle{ u_k=t\, }[/math], we simply call [math]\displaystyle{ P }[/math] an augmenting path.

Let [math]\displaystyle{ f }[/math] be a flow in [math]\displaystyle{ G }[/math]. Suppose there is an augmenting path [math]\displaystyle{ P=u_0u_1\cdots u_k }[/math], where [math]\displaystyle{ u_0=s }[/math] and [math]\displaystyle{ u_k=t }[/math]. Let [math]\displaystyle{ \epsilon\gt 0 }[/math] be a positive constant satisfying

• [math]\displaystyle{ \epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1}) }[/math] for all forward edges [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math] in [math]\displaystyle{ P }[/math];
• [math]\displaystyle{ \epsilon \le f(u_{i+1},u_i) }[/math] for all reverse edges [math]\displaystyle{ (u_{i+1},u_i)\in E }[/math] in [math]\displaystyle{ P }[/math].

Due to the definition of augmenting path, we can always find such a positive [math]\displaystyle{ \epsilon }[/math].

Increase [math]\displaystyle{ f(u_i,u_{i+1}) }[/math] by [math]\displaystyle{ \epsilon }[/math] for all forward edges [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math] in [math]\displaystyle{ P }[/math] and decrease [math]\displaystyle{ f(u_{i+1},u_i) }[/math] by [math]\displaystyle{ \epsilon }[/math] for all reverse edges [math]\displaystyle{ (u_{i+1},u_i)\in E }[/math] in [math]\displaystyle{ P }[/math]. Denote the modified flow by [math]\displaystyle{ f' }[/math]. It can be verified that [math]\displaystyle{ f' }[/math] satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow [math]\displaystyle{ f' }[/math]

[math]\displaystyle{ \sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}\gt \sum_{v:(s,v)\in E}f_{sv} }[/math].

Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.

Lemma

A flow [math]\displaystyle{ f }[/math] is maximum if and only if there are no augmenting paths.

Proof. We have already proved the "only if" direction above. Now we prove the "if" direction. Let [math]\displaystyle{ S=\{u\in V\mid \exists\text{an augmenting path to }u\} }[/math]. Clearly [math]\displaystyle{ s\in S }[/math], and since there is no augmenting path [math]\displaystyle{ t\not\in S }[/math]. Therefore, [math]\displaystyle{ (S,\bar{S}) }[/math] defines an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut. We claim that [math]\displaystyle{ \sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math], that is, the value of flow [math]\displaystyle{ f }[/math] approach the value of the cut [math]\displaystyle{ (S,\bar{S}) }[/math] defined above. By the above lemma, this will imply that the current flow [math]\displaystyle{ f }[/math] is maximum. To prove this claim, we first observe that [math]\displaystyle{ \sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu} }[/math]. This identity is implied by the flow conservation constraint, and holds for any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut [math]\displaystyle{ (S,\bar{S}) }[/math]. We then claim that [math]\displaystyle{ f_{uv}=c_{uv} }[/math] for all [math]\displaystyle{ u\in S,v\not\in S, (u,v)\in E }[/math]; and [math]\displaystyle{ f_{vu}=0 }[/math] for all [math]\displaystyle{ u\in S,v\not\in S, (v,u)\in E }[/math]. If otherwise, then the augmenting path to [math]\displaystyle{ u }[/math] apending [math]\displaystyle{ uv }[/math] becomes a new augmenting path to [math]\displaystyle{ v }[/math], which contradicts that [math]\displaystyle{ S }[/math] includes all vertices to which there exist augmenting paths. Therefore, [math]\displaystyle{ \sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu} = \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math]. As discussed above, this proves the theorem. [math]\displaystyle{ \square }[/math]

The max-flow min-cut theorem

Max-Flow Min-Cut Theorem

In a flow network, the maximum value of any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow equals the minimum value of any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut.

Proof. Let [math]\displaystyle{ f }[/math] be a flow with maximum value, so there is no augmenting path. Again, let [math]\displaystyle{ S=\{u\in V\mid \exists\text{an augmenting path to }u\} }[/math]. As proved above, [math]\displaystyle{ (S,\bar{S}) }[/math] forms an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut, and [math]\displaystyle{ \sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math], that is, the value of flow [math]\displaystyle{ f }[/math] equals the value of cut [math]\displaystyle{ (S,\bar{S}) }[/math]. Since we know that all [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flows are not greater than any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut, the value of flow [math]\displaystyle{ f }[/math] equals the minimum value of any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut. [math]\displaystyle{ \square }[/math]

Flow Integrality Theorem

Let [math]\displaystyle{ (G,c,s,t) }[/math] be a flow network with integral capacity [math]\displaystyle{ c }[/math]. There exists an integral flow which is maximum.

Proof. Let [math]\displaystyle{ f }[/math] be an integral flow of maximum value. If there is an augmenting path, since both [math]\displaystyle{ c }[/math] and [math]\displaystyle{ f }[/math] are integral, a new flow can be constructed of value 1+the value of [math]\displaystyle{ f }[/math], contradicting that [math]\displaystyle{ f }[/math] is maximum over all integral flows. Therefore, there is no augmenting path, which means that [math]\displaystyle{ f }[/math] is maximum over all flows, integral or not. [math]\displaystyle{ \square }[/math]

Unimodularity

Integer Programming

Consider the maximum integral flow problem: given as input a flow network [math]\displaystyle{ (G(V,E),c,s,t) }[/math] where for every [math]\displaystyle{ uv\in E }[/math] the capacity [math]\displaystyle{ c_{uv} }[/math] is integer. We want to find the integral flow [math]\displaystyle{ f:E\rightarrow\mathbb{Z} }[/math] with maximum value.

The mathematical programming for the problem is:

[math]\displaystyle{ \begin{align} \text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\ \begin{align} \text{subject to} \\ \\ \\ \\ \\ \end{align} \quad & \begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\ \sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\ f_{uv}&\in\mathbb{N} &\quad& \forall (u,v)\in E \end{align} \end{align} }[/math]

where [math]\displaystyle{ \mathbb{N} }[/math] is the set of all nonnegative integers. Compared to the LP for the max-flow problem, we just replace the last line [math]\displaystyle{ f_{uv}\ge 0 }[/math] with [math]\displaystyle{ f_{uv}\in\mathbb{N} }[/math]. The resulting optimization is called an integer programming (IP), or more specific integer linear programming (ILP).

Due to the Flow Integrality Theorem, when capacities are integers, there must be an integral flow whose value is maximum among all flows (integral or not). This means the above IP can be efficiently solved by solving its LP-relaxation. This is usually impossible for general IPs.

Generally, an IP of canonical form is written as

[math]\displaystyle{ \begin{align} \text{maximize} \quad& \boldsymbol{c}^T\boldsymbol{x}\\ \begin{align} \text{subject to} \\ \\ \\ \end{align} \quad & \begin{align} A\boldsymbol{x} &\ge\boldsymbol{b} \\ \boldsymbol{x}&\ge \boldsymbol{0}\\ \boldsymbol{x}&\in\mathbb{Z}^n \end{align} \end{align} }[/math]

The following IP solves 3SAT:

[math]\displaystyle{ \begin{align} \text{maximize} \quad& \sum_{i=1}^mz_i\\ \begin{align} \text{subject to} \\ \\ \\ \\ \end{align} \quad & \begin{align} z_i &\le y_{i_1}+y_{i_2}+y_{i_3} &\quad& \forall 1\le i\le m\\ y_{i_j}&\le x_{i_j} &\quad& \text{if }\ell_{i_j}=x_{i_j} \\ y_{i_j}&\le 1-x_{i_j} &\quad& \text{if }\ell_{i_j}=\neg x_{i_j} \\ x_j,z_j &\in\{0,1\} &\quad& \forall 1\le i\le m, 1\le j\le n \end{align} \end{align} }[/math]

Since 3SAT is NP-hard (actually it is the first problem known to be NP-hard), generally IP is NP-hard.

Integrality of polytopes

A point in an [math]\displaystyle{ n }[/math]-dimensional space is integral if all its coordinates are integers.

A polyhedron is said to be integral if all its vertices are integral.

There always exists an optimal solution which is a vertex in [math]\displaystyle{ P }[/math]. For integral [math]\displaystyle{ P }[/math], all vertices are integral.

Theorem (Hoffman 1974)

If a polyhedron [math]\displaystyle{ P }[/math] is integral then for all integer vectors [math]\displaystyle{ \boldsymbol{c} }[/math] there is an optimal solution to [math]\displaystyle{ \max\{\boldsymbol{c}^T\boldsymbol{x}\mid \boldsymbol{x}\in P\} }[/math] which is integral.

Unimodularity and total unimodularity

Definition (Unimodularity)

An [math]\displaystyle{ n\times n }[/math] integer matrix [math]\displaystyle{ A }[/math] is called unimodular if [math]\displaystyle{ \det(A)=\pm1 }[/math]. An [math]\displaystyle{ m\times n }[/math] integer matrix [math]\displaystyle{ A }[/math] is called total unimodular if every square submatrix [math]\displaystyle{ B }[/math] of [math]\displaystyle{ A }[/math] has [math]\displaystyle{ \det(B)\in\{1,-1,0\} }[/math], that is, every square, nonsingular submatrix of [math]\displaystyle{ A }[/math] is unimodular.

Theorem

Let [math]\displaystyle{ A }[/math] be an [math]\displaystyle{ m\times n }[/math] integer matrix. If [math]\displaystyle{ A }[/math] is totally unimodualr, then for any integer vector [math]\displaystyle{ \boldsymbol{b}\in\mathbb{Z}^n }[/math] the polyhedron [math]\displaystyle{ \{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\} }[/math] is integral.

Proof. Let [math]\displaystyle{ B }[/math] be a basis of [math]\displaystyle{ A }[/math], and let [math]\displaystyle{ \boldsymbol{b}' }[/math] be the corresponding coordinates in [math]\displaystyle{ \boldsymbol{b} }[/math]. A basic solution is formed by [math]\displaystyle{ B^{-1}\boldsymbol{b}' }[/math] and zeros. Since [math]\displaystyle{ A }[/math] is totally unimodular and [math]\displaystyle{ B }[/math] is a basis thus nonsingular, [math]\displaystyle{ \det(B)\in\{1,-1,0\} }[/math]. By Cramer's rule, [math]\displaystyle{ B^{-1} }[/math] has integer entries, thus [math]\displaystyle{ B^{-1}\boldsymbol{b}' }[/math] is integral. Therefore, any basic solution of [math]\displaystyle{ A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0} }[/math] is integral, which means the polyhedron [math]\displaystyle{ \{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\} }[/math] is integral. [math]\displaystyle{ \square }[/math]

Theorem (Hoffman-Kruskal 1956)

Let [math]\displaystyle{ A }[/math] be an [math]\displaystyle{ m\times n }[/math] integer matrix. If [math]\displaystyle{ A }[/math] is totally unimodualr, then for any integer vector [math]\displaystyle{ \boldsymbol{b}\in\mathbb{Z}^n }[/math] the polyhedron [math]\displaystyle{ \{\boldsymbol{x}\in\mathbb{R}^n\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\} }[/math] is integral.

Proof. Let [math]\displaystyle{ A'=\begin{bmatrix}A & -I\end{bmatrix} }[/math]. We claim that [math]\displaystyle{ A' }[/math] is also totally unimodular. Any square submatrix [math]\displaystyle{ B }[/math] of [math]\displaystyle{ A }[/math] can be written in the following form after permutation: [math]\displaystyle{ B=\begin{bmatrix} C & 0\\ D & I \end{bmatrix} }[/math] where [math]\displaystyle{ C }[/math] is a square submatrix of [math]\displaystyle{ A }[/math] and [math]\displaystyle{ I }[/math] is identity matrix. Therefore, [math]\displaystyle{ \det(B)=\det(C)\in\{1,-1,0\} }[/math], thus [math]\displaystyle{ A' }[/math] is totally unimodular. Add slack variables to transform the constraints to the standard form [math]\displaystyle{ A'\boldsymbol{z}=\boldsymbol{b},\boldsymbol{z}\ge\boldsymbol{0} }[/math]. The polyhedron [math]\displaystyle{ \{\boldsymbol{x}\mid A\boldsymbol{x}\ge\boldsymbol{b}, \boldsymbol{x}\ge \boldsymbol{0}\} }[/math] is integral if the polyhedron [math]\displaystyle{ \{\boldsymbol{z}\mid A'\boldsymbol{z}=\boldsymbol{b}, \boldsymbol{z}\ge \boldsymbol{0}\} }[/math] is integral, which is implied by the total unimodularity of [math]\displaystyle{ A'\, }[/math]. [math]\displaystyle{ \square }[/math]