8.1 Why the Ford-Fulkerson algorithm looks so familiar

Question 1

How does a biparite matching reduce to a flow network

Answer 1

• Include source and sink
• Direct edges, weight 1
• Augmenting path => matched and non matching since backward edge

Question 2

How to simulate rational weights in a flow network

Answer 2

Multiply each weight by k : all integers

Note: Runtime is prop to F*(v) so prime numbers can mess up runtime

Question 3

Edmonds-Karp: when to use it, what is its runtime and how its different to FF (flow networks)

Answer 3

• When we have irrational edge capacities (potentially bad numbers) - FF won’t terminate
• O(|V||E|^2) => in practice worse than FF
• Use BFS rather than DFS