The set of vertices reachable from source s in the residual graph is one part of the partition. Cut capacity cap(A,B)=∑out Ac(e).
∣f∣=eout of X∑f(e)−einto X∑f(e)
maxflow = Min cap(A,B).
Ford-Fulkerson
Given (G,s,t,c∈N+), start with f(u,v)=0 and Gf=G. While an augmenting path is in Gf, find a bottleneck. Augment the flow along this path and update the residual graph Gf. O(∣f∣(V+E)).
Edmond-Karp
Ford-Fulkerson, but choose the shortest augmenting path.
For any flow f and any (A,B) cut, ∣f∣≤cap(A,B). For any flow f and any (A,B) cut, ∣f∣=∑f(s,v)=
Solving by Reduction
To reduce a problem Y to a problem X (Y≤pX) we want a function f that maps Y to X such that f is a polynomial time computable and ∀y∈Y is solvable if and only if f(y)∈X 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.
O(∣f∣(E′+V′))
∣f∣=V
V′=2V+2
E′=E+2V
O(V(E+2V+2V+2))=O(VE
Circulation
d(v)>0 if demand
d(v)<0 if supply
Capacity Constraint 0≤f(e)≤c(e)
Conservation Constraint fin(v)−fout(v)=d(v).
For every feasible circulation ∑v∈Vd(v)=0, there is a feasible circulation with demands d(v) in if and only if the maximum flow in has value .
Circulation with Demands and Lower Bounds.
Capacity Constraint l(e)≤f(e)≤c(e)
Conservation Constraint fin(v)−fout(v)=d(v)
Given G with lower bounds, we subtract the lower bound l(e) from the capacity of each edge.
Subtract f0in(v)−f0out from the demand of each node.
Solve the circulation problem on this new graph to get a flow f.
Add l(e) to every f(e) to get a flow for the original graph.
Existence of Linear Programming Solution.
Given an Linear Programming problem with a feasible set and an objective function P.
If S is empty, Linear Programming has no solution.``
If S is unbounded, Linear Programming may or may not have the solution.
If S is bounded, Linear Programming has one or more solutions.
Standard Form Linear Programming
max(c1x1+⋯+cnxn)
subject to
a11x1+⋯+a
all the way to
am1x1+⋯+a.
Also, x1≥0,⋯,xn≥0.
Matrix Form Linear Programming
max(cTx)
subject to
Ax≤b
x≥0
x∈R
Integer Linear Program
all variables ∈N
is NP-Hard
Dual Program
min(bTy)
subject to
ATy≥c
y≥0
y∈R
Weak Duality
The optimum of the dual is an upper bound to the optimum of the primal.
OPT(primal)≤OPT(dual).
Strong duality
Let P and D be primal and dual Linear Programming correspondingly. If P and D are feasible, then cTx=bTy.
If a standard problem and its dual are feasible, both are feasibly bounded. If one problem has an unbounded solution, then the dual of that problem is infeasible.
Decision Knapsack is NP-complete, whereas undecidable problems like Halting problems are only NP-Hard (not NP).
X is NP-Hard if ∀Y∈NP and Y≤pX.
X is NP-complete if X is NP-Hard and X∈NP.
If P = NP, then P = NP-complete.
NP Problems can be solved in poly-time with NDTM.
NP Problems can be verified in poly-time by DTM.
Polynomial Reduction
To reduce a decision problem Y to a decision problem X (Y≤pX), find a function f that maps Y to X such that f is poly-time computable and ∀y∈Y is YES if and only if f(y)∈X is YES.
Proving NP-Complete
Show X is in NP, Pick problem NP-complete Y, and show Y≤pX.