I am very happy that I had the chance today to attend a lecture held by Jack Edmonds, who is regarded as one of the most important contributors to the field of combinatorial optimization.

During his talk, Jack asked us to think about how to reduce the shortest path problem on directed graphs with rational costs on the edges to the assignment problem. I thought a bit about it and want to present my solution here.

First of all, let's recap what the shortest path problem and the assignment problem is.

The Shortest Path Problem

Given a directed graph $D=(V,A)$, a cost function $c_D : A \rightarrow \mathbb{R}$ and two designated nodes $s,t$ the task is to find a path

$P=(v_1,v_2,...,v_n) \in V^{n}$ with

$v_1=s, v_n=t, v_i \neq v_j \forall i\neq j$

$(v_i,v_{i+1}) \in A ~ \forall i=1,...,n-1$ such that the cost function

$c_D(P) := \sum_{i=1}^{n-1}c_D(v_i,v_{i+1})$ is minimized.

In fact we assume that the graph does not contain negative circuits. Otherwise the problem would be equivalent to the longest path problem with cost function $-c_D$, which is NP-hard.

The Assignment Problem

Given two sets $X$ and $Y$ of equal size and a cost function $c_A : X\times Y \rightarrow \mathbb{R}$. Find a perfect matching $M$ such that the cost function $\sum_{(x,y)\in\ M}c_A(x,y)$ is minimized.

And here comes the reduction

First, we will construct a bipartite graph $B=(X\bigsqcup Y,E)$ and cost function $c$ as follows:

$X:=\{x_v:v\in V\setminus\{s\}\}$

$Y:=\{y_v:v\in V\setminus\{t\}\}$

$E:=\{\{y_v,x_w\}:(v,w)\in A\}\bigcup \{\{x_v,y_v\}:v\in V\setminus\{s,t\}\}$

$c : E \rightarrow \mathbb{R}, \{y_v,x_w\} \mapsto \left\{\begin{array}{cl} c_D(v,w), & \mbox{if }(v,w)\in A\\ 0, & \mbox{otherwise} \end{array}\right.$

Proposition 1

Every perfect matching $M$ in $B$ induces a $(s,t)$-Path $P=(v_1,v_2,...,v_n)$ in $D$ constructed by the following algorithm.

$Let~m(v)~be~the~node~that~is~matched~to~v~in~M.$
$p:=s$
$i:=1$
$while~(x_p \neq x_t)~ do$
$v_i:=p$
$x_p:=m(y_p)$
$i++$

Proof

Because $M$ is a matching, the constructed path $P$ cannot have a circuit, i.e. a $v_j$ does not repeat. The algorithm stops as soon as it reaches $t$ and because the set of nodes is finite, the algorithm has to stop. It follows that $P$ is a $(s,t)$-path.

Proposition 2

Let $P$ be a $(s,t)$-path in $D$ then

$M:=\{\{x_v,y_v\}:v\notin P\}\cup \{\{x_v,y_w\}:(v,w) \in P\}$

is a perfect matching in $B$.

Proof

First of all recognize that $X$ and $Y$ have got the same size. Because a node $v$ either has an successor in $P$, is $t$ or is not in $P$, every node in $X$ gets covered. Because $P$ does not contain a circuit, two edges in $M$ cannot be adjacent and thus every node in $Y$ gets covered. It follows that $M$ is a perfect matching.

Finally

Taking proposition 1 and 2 together, we can reduce the shortest path problem to the assignment problem by doing the following:

1. Construct $B$ like shown above
2. Find a cost-minimal perfect matching $M$
3. Construct a path in $D$ with the algorithm from proposition 1

Proposition 1 tells us that step 3 will succeed and proposition 2 tells us that while doing step 2 we consider all possible paths. As $M$ has got minimal cost, so $P$ has. Recap that we required the absence of negative circuits.