- Optimal substructure. The optimal solution to a problem consists of optimal solutions to subproblems.
- Overlapping subproblems. few subproblems in total, many recurring instances of each.
shortest path, negative possible.
Chain Matrix Multiplication
The set of vertices reachable from source s in the residual graph is one part of the partition. Cut capacity .
- maxflow = Min .
Given , start with and . While an augmenting path is in , find a bottleneck. Augment the flow along this path and update the residual graph . .
Ford-Fulkerson, but choose the shortest augmenting path.
For any flow and any cut, . For any flow and any cut,
Solving by Reduction
To reduce a problem to a problem () we want a function that maps to such that is a polynomial time computable and is solvable if and only if is solvable.
Reduction to NF
Describe how to construct a flow network. Claim "This is feasible if and only if the max flow is …". Prove both directions.
Bipartite to Max Flow
- Max Matching ⟹ Max Flow. If k edges are matched, then there is a flow of value k.
- Max matching ⟸ Max flow. If there is a flow f of value k, there is a matching with k edges.