# 7 - Graph Matching 3 Flashcards

1
Q

What is a minimum cut?

A

A minimum cut is a cut whose capacity is minimum along all possible cuts

2
Q

Proving the ‘if’ part of the Augmenting Path Theorem

A

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

3
Q

What is the Max Flow - Min Cut Theorem?

A

Value of a maximum flow is equal to the capacity of a minimum cut

4
Q

Example of application of Max Flow - Min Cut theorem

A
5
Q

How to find a maximum flow?

A
• Start with flow 0 on all edges
• Repeatedly search for augmenting path
• augment the flow along this path
• Until no path found
6
Q

Searching for augmenting path - what is the residual graph?

A
• 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’
7
Q

How is the residual graph defined?

A
• 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>
• (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
8
Q

Example residual graph

A
9
Q

What is the Ford-Fulkerson algorithm?

A
10
Q

What is the complexity of Ford-Fulkerson algorithm?

A
• 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)
11
Q

Worst case example

A
12
Q

How to improve worst case of Ford-Fulkerson algorithm?

A
• 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|)
13
Q

Example for improving worst case

A

Check slides

14
Q

Faster algorithm for maximum matching

A
• 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’
15
Q

Example of faster algorithm for maximum matching

A