shortest path IP

Work in Progress

Concept

A graph has vertices and edges; denotes edges incident to . A path has distinct vertices, while a walk may repeat them. With edge costs , path or matching cost is over selected edges.

A matching has no shared endpoints and is perfect if every vertex is covered. With iff is selected, minimum-cost perfect matching is

Shortest path cuts

Endpoint edges

  • set of edges with exactly one vertex in

It is an -cut when and . Every -path crosses every such cut. Conversely, an edge set intersecting every -cut contains an -path: otherwise vertices reachable from define an unhit cut.

-cuts

  • when removing a subset of edges removes all paths between and
S = \{ s \} \to\delta(S) = \{ sa, sb \}\text{ is an }s,t \text{-cut}$$ ```tikz \usepackage{tikz} \usetikzlibrary{arrows.meta,positioning,calc} \tikzstyle{vertex}=[draw,circle,minimum size=18pt,inner sep=0pt] \begin{document} \begin{tikzpicture}[thick] \node[vertex] (a) {a}; \node[vertex,below right=of a] (t) {t}; \node[vertex,below left=of a] (s) {s}; \node[vertex,below right=of s] (b) {b}; \draw[-,red] (s) -- (a); \draw[-,red] (s) -- (b); \draw[-] (a) -- (b); \draw[-] (a) -- (t); \draw[-] (b) -- (t); \end{tikzpicture} \end{document} ```

S = { s,a } \to\delta(S) = { sb, at, ab }\text{ is an }s,t
\text{-cut}$$

atsb
atsb

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

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

atsb34122
𝟙𝟘

All s,t-cuts of a graph

atbscd213121244