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 , a cost function
and two designated nodes
the task is to find a path
with
such that the cost function
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 , which is NP-hard.
The Assignment Problem
Given two sets and
of equal size and a cost function
. Find a perfect matching
such that the cost function
is minimized.
And here comes the reduction
First, we will construct a bipartite graph and cost function
as follows:
Proposition 1
Every perfect matching in
induces a
-Path
in
constructed by the following algorithm.
Proof
Because is a matching, the constructed path
cannot have a circuit, i.e. a
does not repeat. The algorithm stops as soon as it reaches
and because the set of nodes is finite, the algorithm has to stop. It follows that
is a
-path.
Proposition 2
Let be a
-path in
then
is a perfect matching in .
Proof
First of all recognize that and
have got the same size. Because a node
either has an successor in
, is
or is not in
, every node in
gets covered. Because
does not contain a circuit, two edges in
cannot be adjacent and thus every node in
gets covered. It follows that
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:
- Construct
like shown above
- Find a cost-minimal perfect matching
- Construct a path in
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 has got minimal cost, so
has. Recap that we required the absence of negative circuits.