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.