shortest path IP
Concept
A graph
A matching has no shared endpoints and is perfect if every vertex is covered. With
Shortest path cuts
Endpoint edges
- set of edges with exactly one vertex in
It is an
- when removing a subset of edges removes all paths between
and
S = { s,a } \to\delta(S) = { sb, at, ab }\text{ is an }s,t
\text{-cut}$$
even though there is no path from
to , there could still be an edge in the greater
Path and cut
- an
-path overlaps with an -cut, by 1 edge
Constructing a path from
Shortest-path IP
- binary variable for each edge
- full IP
each s,t-cut gives an additional constraint
For positive costs, an optimum contains a shortest path and no costly surplus is needed. This cut formulation later yields the dual in shortest path duality.
Application
Shortest path example
All s,t-cuts of a graph