shortest path duality

Work in Progress

Concept

sjahibcgtd

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 to -cuts:

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 ; zero-slack edges are equality edges.

The primal-dual shortest-path algorithm grows reachable vertices through equality edges while raising one cut width.

Invariants: stays dual feasible; every arc is tight; active cuts have no entering arc; every vertex in has a directed path from ; arcs have both ends in after expansion. At least one vertex enters per iteration. The output path uses equality edges and crosses each active cut exactly once, so its length equals . It is shortest, and the cut LP has an integral optimum.

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
atbscd213121244
  • step 1: start with 0 for all width assignments
atbscd213121244
  • step 2: relax vertex c
atbscd213121244

remeber previous relaxations made to the edges
when there are multiple completely relaxed edges, just pick one

  • step 3: relax vertex a
atbscd213121244
  • step 4: relax vertex d
atbscd213121244
  • step 5: relax vertex b
atbscd213121244
  • step 5: relax vertex t, return directed path
atbscd213121244

Application

Dual of the shortest path example

atsb34122
𝟙𝟘

we can relax the integrality constraints without changing the optimal values for this IP
note: this is not true for all IPs

𝟙𝟘