7 - Graph Matching 3 Flashcards
What is a minimum cut?
A minimum cut is a cut whose capacity is minimum along all possible cuts
Proving the ‘if’ part of the Augmenting Path Theorem
Define a cut C = {(u,v) E : u Aand v B} such that val(f) = cap(C) Then f must be a maximum flow (not proved here), because no additional flow can get from a vertex in A to a vertex in B Let G = (V,E) be a network with source s, sink t, capacity function c and flow f, and suppose that f admits no augmenting path Let AV be the set of vertices that we can reach along a “partial augmenting path” from s, and let B=V \ A (so the absence of a complete augmenting path implies that s A and t B) Define C = {(u,v)E : uA and vB} Then it must be the case that f(u,v)=c(u,v) for each (u,v)C, and f(v,u)=0 for each (v,u)E such that vB and uA - otherwise we could extend some partial augmenting path to reach a vertex in B It follows that val(f)=cap(C) (not proved here), and therefore that f is a maximum flow This is the essence of the so-called Max Flow – Min Cut Theorem
What is the Max Flow - Min Cut Theorem?
Value of a maximum flow is equal to the capacity of a minimum cut
Example of application of Max Flow - Min Cut theorem
How to find a maximum flow?
- Start with flow 0 on all edges
- Repeatedly search for augmenting path
- augment the flow along this path
- Until no path found
Searching for augmenting path - what is the residual graph?
- Let G=(V,E) be a network with capacity function c, and let f be a flow in G
- The residual graph G’=(V’,E’) with respect to G and f is a directed graph with capacity function c’
How is the residual graph defined?
- V’=V
- G’ has the same vertex set as G
- (u,v)E’ if and only if:
- (u,v)E and f(u,v)<c>
<li>so (u,v) can be a forward edge in an augmenting path</li>
<li>in this case define c'(u,v) = c(u,v) - f(u,v)</li>
</c>
- (u,v)E and f(u,v)<c>
- (v,u)E and f(v,u)>0
- so (u,v) can be a backward edge in an augmenting path
- in this case define c’(u,v) = f(v,u)
- A directed path from s to t in the residual graph G’ corresponds to an augmenting path with respect to f in G
Example residual graph
What is the Ford-Fulkerson algorithm?
What is the complexity of Ford-Fulkerson algorithm?
- Initialisation is O(|E|)
- During loop iteration:
- Build residual graph - O(|V| + |E|)
- Search for directed path s to t
- O(|V| + |E|) using breadth first or depth first search
- Augment along path if found - O(|E|)
- Every vertex is on a directed path s to t, therefor |V| = O(|E|)
- No. loop iterations is <= val of max flow
- worst case m=1 during every loop iteration, so flow only increases by 1 each iteration
- Overall complexity is O(|E|.max flow)
Worst case example
How to improve worst case of Ford-Fulkerson algorithm?
- At point (†) in Ford-Fulkerson, use breadth-first search to find the shortest augmenting path (i.e. with the smallest number of edges)
- Edmonds and Karp (1972): if we follow this practice, number of times algorithm searches for an augmenting path is O(|V||E|)
- Therefore Ford-Fulkerson algorithm can be implemented to run in O(|V||E|2)=O(|E|3) time
- Fastest algorithm to date: Orlin (2013): O(|V||E|)
Example for improving worst case
Check slides
Faster algorithm for maximum matching
- Input: Bipartite graph G
- Output: Maximum matching M in G
- Reduce this problem to a network flow problem:
- Let G=(V,E) be a bipartite graph, where G has bipartition V=U W
- Form a directed graph G’=(V’,E’) as follows:
- V’=V{s,t} for two new vertices s, t
- E’={(s,u) : uU} {(u,w) : uU wW {u,w}E} {(w,t) : wW}
- All edges in G’ have capacity 1
- Claim: The cardinality of a maximum matching in G is equal to the value of a maximum flow in G’
Example of faster algorithm for maximum matching
