组合数学 (Spring 2013)/Flow and matching
Flow and Cut
Flows
An instance of the maximum flow problem consists of:
- a directed graph ;
- two distinguished vertices (the source) and (the sink), where the in-degree of and the out-degree of are both 0;
- the capacity function which associates each directed edge a nonnegative real number called the capacity of the edge.
The quadruple is called a flow network.
A function is called a flow (to be specific an - flow) in the network if it satisfies:
- Capacity constraint: for all .
- Conservation constraint: for all .
The value of the flow is .
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.
Cuts
Definition - Let be a flow network. Let . We call an - cut if and .
- The value of the cut (also called the capacity of the cut) is defined as .
A fundamental fact in flow theory is that cuts always upper bound flows.
Lemma - Let be a flow network. Let be an arbitrary flow in , and let be an arbitrary - cut. Then
- ,
- that is, the value of any flow is no greater than the value of any cut.
- Let be a flow network. Let be an arbitrary flow in , and let be an arbitrary - cut. Then
Proof. By the definition of - cut, and . Due to the conservation of flow,
On the other hand, summing flow over edges,
Therefore,
Augmenting paths
Definition (Augmenting path) - Let be a flow in . An augmenting path to is a sequence of distinct vertices , such that
- ;
- and each pair of consecutive vertices in corresponds to either a forward edge or a reverse edge , and
- when corresponds to a forward edge , and
- when corresponds to a reverse edge .
- If , we simply call an augmenting path.
- Let be a flow in . An augmenting path to is a sequence of distinct vertices , such that
Let be a flow in . Suppose there is an augmenting path , where and . Let be a positive constant satisfying
- for all forward edges in ;
- for all reverse edges in .
Due to the definition of augmenting path, we can always find such a positive .
Increase by for all forward edges in and decrease by for all reverse edges in . Denote the modified flow by . It can be verified that satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow
- .
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 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 . Clearly , and since there is no augmenting path . Therefore, defines an - cut.
We claim that
- ,
that is, the value of flow approach the value of the cut defined above. By the above lemma, this will imply that the current flow is maximum.
To prove this claim, we first observe that
- .
This identity is implied by the flow conservation constraint, and holds for any - cut .
We then claim that
- for all ; and
- for all .
If otherwise, then the augmenting path to apending becomes a new augmenting path to , which contradicts that includes all vertices to which there exist augmenting paths.
Therefore,
- .
As discussed above, this proves the theorem.
Max-Flow Min-Cut
The max-flow min-cut theorem
Max-Flow Min-Cut Theorem - In a flow network, the maximum value of any - flow equals the minimum value of any - cut.
Proof. Let be a flow with maximum value, so there is no augmenting path.
Again, let
- .
As proved above, forms an - cut, and
- ,
that is, the value of flow equals the value of cut .
Since we know that all - flows are not greater than any - cut, the value of flow equals the minimum value of any - cut.
Flow Integrality Theorem
Flow Integrality Theorem - Let be a flow network with integral capacity . There exists an integral flow which is maximum.
Proof. Let be an integral flow of maximum value. If there is an augmenting path, since both and are integral, a new flow can be constructed of value 1+the value of , contradicting that is maximum over all integral flows. Therefore, there is no augmenting path, which means that is maximum over all flows, integral or not.
Applications: Menger's theorem
Given an undirected graph and two distinct vertices , a set of edges is called an - cut, if deleting edges in disconnects and .
A simple path from to is called an - path. Two paths are said to be edge-disjoint if they do not share any edge.
Theorem (Menger 1927) - Let be an arbitrary undirected graph and be two distinct vertices. The minimum size of any - cut equals the maximum number of edge-disjoint - paths.
Proof. Construct a directed graph from as follows: replace every undirected edge that by two directed edges and ; replace every undirected edge by , and very undirected edge by . Then assign every directed edge with capacity 1.
It is easy to verify that in the flow network constructed as above, the followings hold:
- An integral - flow corresponds to a set of - paths in the undirected graph , where the value of the flow is the number of - paths.
- An - cut in the flow network corresponds to an - cut in the undirected graph with the same value.
The Menger's theorem follows as a direct consequence of the max-flow min-cut theorem.
Applications: König-Egerváry theorem
Let be a graph. An edge set is called a matching if no edge in shares any vertex. A vertex set is called a vertex cover if for any edge , either or .
Theorem (König 1936) - In any bipartite graph , the size of a maximum matching equals the size of a minimum vertex cover.
We now show how a reduction of bipartite matchings to flows.
Construct a flow network as follows:
- where and are two new vertices.
- For ever , add to ; for every , add to ; and for every , add to .
- Let for every and for every . Let for every bipartite edges .
Lemma - The size of a maximum matching in is equal to the value of a maximum - flow in .
Proof. Given an integral - flow in , let . Then must be a matching since for every . To see this, observe that there is at most one that , because of that and conservation of flows. The same holds for vertices in by the same argument. Therefore, each flow corresponds to a matching.
Given a matching in bipartite graph , define an integral flow as such: for , if and if otherwise; for , if for some and if otherwise; for , if for some and if otherwise.
It is easy to check that is valid - flow in . Therefore, there is an one-one correspondence between flows in and matchings in . The lemma follows naturally.
We then establish a correspondence between - cuts in and vertex covers in .
Suppose is an - cut in .
Lemma - The size of a minimum vertex cover in is equal to the value of a minimum - cut in .
Proof. Let be an - cut of minimum capacity in . Then must be finite since gives us an - cut whose capacity is which is finite. Therefore, no edge has and , i.e., for all , either or . Therefore, is a vertex cover in , whose size is
- .
The last term is the capacity of the minimum - cut .
The König-Egerváry theorem then holds as a consequence of the max-flow min-cut theorem.
Linear Programming
Consider the following LP:
Let be the value of the optimal solution. We want to estimate the upper and lower bound of .
Since is the minimum over the feasible set, every feasible solution forms an upper bound for . For example is a feasible solution, thus .
For the lower bound, the optimal solution must satisfy the two constraints:
Since the 's are restricted to be nonnegative, term-by-term comparison of coefficients shows that
The idea behind this lower bound process is that we are finding suitable nonnegative multipliers (in the above case the multipliers are all 1s) for the constraints so that when we take their sum, the coefficient of each in the sum is dominated by the coefficient in the objective function. It is important to ensure that the multipliers are nonnegative, so they do not reverse the direction of the constraint inequality.
To find the best lower bound, we need to choose the multipliers in such a way that the sum is as large as possible. Interestingly, the problem of finding the best lower bound can be formulated as another LP:
Here and were chosen to be nonnegative multipliers for the first and the second constraint, respectively. We call the first LP the primal program and the second LP the dual program. By definition, every feasible solution to the dual program gives a lower bound for the primal program.
Duality
Given an LP in canonical form, called the primal LP:
the dual LP is defined as follows:
LP for maximum flow
In the last lecture, we defined the maximum flow problem, whose LP is
where directed graph is the flow network, is the source, is the sink, and is the capacity of directed edge .
We add a new edge from to to , and let the capacity be . Let be the new edge set. The LP for the max-flow problem can be rewritten as:
The second set of inequalities seem weaker than the original conservation constraint of flows, however, if this inequality holds at every node, then in fact it must be satisfied with equality at every node, thereby implying the flow conservation.
To obtain the dual program we introduce variables and corresponding to the two types of inequalities in the primal. The dual LP is:
It is more helpful to consider its integer version:
Suppose that for the flow LP, the integral optimal solution always equals the fractional optimal solution (we will show this later). The variables defines a bipartition of vertex set . Let . The complement .
For 0/1-valued variables, the only way to satisfy is to have and . Therefore, is an - cut.
In an optimal solution, if and only if and . Therefore, the objective function of an optimal solution is the capacity of the minimum - cut .
LP duality theorem
Consider the primal LP:
Its dual LP is:
Theorem - The dual of a dual is the primal.
Proof. The dual program can be written as the following minimization in canonical form:
Its dual is:
which is equivalent to the primal:
We have shown that feasible solutions of a dual program can be used to lower bound the optimum of the primal program. This is formalized by the following important theorem.
Theorem (Weak duality theorem) - If there exists an optimal solution to the primal LP:
- then,
- If there exists an optimal solution to the primal LP:
Proof. Let be an arbitrary feasible solution to the primal LP, and be an arbitrary feasible solution to the dual LP.
We estimate in two ways. Recall that and , thus
- .
Since this holds for any feasible solutions, it must also hold for the optimal solutions.
A harmonically beautiful result is that the optimums of the primal LP and its dual are equal. This is called the strong duality theorem of linear programming.
Theorem (Strong duality theorem) - If there exists an optimal solution to the primal LP:
- then,
- If there exists an optimal solution to the primal LP:
Integrality
Consider the maximum integral flow problem: given as input a flow network where for every the capacity is integer. We want to find the integral flow with maximum value.
The mathematical programming for the problem is:
where is the set of all nonnegative integers. Compared to the LP for the max-flow problem, we just replace the last line with . 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
Consider the 3SAT problem. Each instance is a 3CNF(conjunctive normal form): , where each is a clause and each , called a literal, is either a boolean variable or a negation of a boolean variable. We want to determine whether there exists an truth assignment of the boolean variables such that the input formula is satisfied (i.e., is true).
The following IP solves 3SAT:
Since 3SAT is NP-hard (actually it is the first problem known to be NP-hard), generally IP is NP-hard.
Integral polytopes
A point in an -dimensional space is integral if it belongs to , i.e., if all its coordinates are integers.
A polyhedron is said to be integral if all its vertices are integral.
An easy observation is that an integer programming has the same optimal solutions as its LP-relaxation when the polyhedron defined by the LP-relaxation is integral.
Theorem (Hoffman 1974) - If a polyhedron is integral then for all integer vectors there is an optimal solution to which is integral.
Proof. There always exists an optimal solution which is a vertex in . For integral , all vertices are integral.
Unimodularity
Definition (Unimodularity) - An integer matrix is called unimodular if .
- An integer matrix is called total unimodular if every square submatrix of has , that is, every square, nonsingular submatrix of is unimodular.
A totally unimodular matrix defines a integral convex polyhedron.
Theorem - Let be an integer matrix.
- If is totally unimodualr, then for any integer vector the polyhedron is integral.
Proof. Let be a basis of , and let be the corresponding coordinates in . A basic solution is formed by and zeros. Since is totally unimodular and is a basis thus nonsingular, . By Cramer's rule, has integer entries, thus is integral. Therefore, any basic solution of is integral, which means the polyhedron is integral.
Our next result is the famous Hoffman-Kruskal theorem.
Theorem (Hoffman-Kruskal 1956) - Let be an integer matrix.
- If is totally unimodualr, then for any integer vector the polyhedron is integral.
Proof. Let . We claim that is also totally unimodular. Any square submatrix of can be written in the following form after permutation:
where is a square submatrix of and is identity matrix. Therefore,
- ,
thus is totally unimodular.
Add slack variables to transform the constraints to the standard form . The polyhedron is integral if the polyhedron is integral, which is implied by the total unimodularity of .