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