shortest path duality
Concept
Width assignment
- values assigned to s,t-cuts
- minimum “toll” to cross a boundary defined by an s,t-cut
Slack
- leftover cost if an edge were to be relaxed by the width assignment
Dual LP
- maximize width assignments instead
Relaxing integrality in shortest path IP gives a primal LP. Its dual assigns nonnegative widths
Any path crosses every cut, so feasible widths lower-bound every path length. Algebraically this is weak duality for
A path and width assignment of equal value certify mutual optimality. The edge slack is
The primal-dual shortest-path algorithm grows reachable vertices through equality edges while raising one cut width.
Invariants:
Primal-dual shortest path algorithm
- similar to BFS but works on weighted edges with bellman-ford edge relaxation
y <- 0
U <- {s}
while t ∉ U:
choose edge ab with minimum slack among edges in δ(U), a ∈ U, b ∉ U
y_U <- slack_y(ab)
U = U + {b}
make ab directed
return the directed s,t path and y
- example graph
- step 1: start with 0 for all width assignments
- step 2: relax vertex c
remeber previous relaxations made to the edges
when there are multiple completely relaxed edges, just pick one
- step 3: relax vertex a
- step 4: relax vertex d
- step 5: relax vertex b
- step 5: relax vertex t, return directed path
Application
Dual of the shortest path example
we can relax the integrality constraints without changing the optimal values for this IP
note: this is not true for all IPs