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
such that the cost function
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:
Every perfect matching in induces a -Path in constructed by the following algorithm.
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.
Let be a -path in then
is a perfect matching in .
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.
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.