Route inspection problem

In graph theory, a branch of mathematics, the Chinese postman problem (CPP), postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of a (connected) undirected graph. When the graph has an Eulerian circuit (a closed walk that covers every edge once), that circuit is an optimal solution.

Alan Goldman of the U.S. National Bureau of Standards first coined the name 'Chinese Postman Problem' for this problem, as it was originally studied by the Chinese mathematician Mei-Ku Kuan in 1962.^[1]

Eulerian paths and circuits

In order for a graph to have an Eulerian circuit, it will certainly have to be connected.

Suppose we have a connected graph G = (V, E), The following statements are equivalent:

1. All vertices in G have even degree.
2. G consists of the edges from a disjoint union of some cycles, and the vertices from these cycles.
3. G has an Eulerian circuit.

• 1 → 2 can be shown by induction on the number of cycles.
• 2 → 3 can also be shown by induction on the number of cycles, and
• 3 → 1 should be immediate.

An Eulerian path (a walk which is not closed but uses all edges of G just once) exists if and only if G is connected and exactly two vertices have odd valence.

T-joins

Let T be a subset of the vertex set of a graph. An edge set whose odd-degree vertices are the vertices in T is called a T-join. (In a connected graph, a T-join exists if and only if |T| is even.) The T-join problem is to find a smallest T-join. A smallest T-join leads to a solution of the postman problem. A smallest T-join necessarily consists of $\tfrac{1}{2}$|T| paths, no two having an edge in common, that join the vertices of T in pairs. The paths will be such that the total length of all of them is as small as possible. A minimum T-join can be obtained by a weighted matching algorithm that uses O(n³) computational steps.^[2]

Solution

If a graph has an Eulerian circuit (or an Eulerian path), then an Eulerian circuit (or path) visits every edge, and so the solution is to choose any Eulerian circuit (or path).

If the graph is not Eulerian, it must contain vertices of odd degree. By the handshaking lemma, there must be an even number of these vertices. To solve the postman problem we first find a smallest T-join. We make the graph Eulerian by doubling of the T-join. The solution to the postman problem in the original graph is obtained by finding an Eulerian circuit for the new graph.

Variants

A few variants of the Chinese Postman Problem have been studied and shown to be NP-complete.^[3]

• Min Chinese postman problem for mixed graphs: for this problem, some of the edges may be directed and can therefore only be visited from one direction. When the problem is minimal traversal of a digraph it is known as the "New York Street Sweeper problem."
• Min k-Chinese postman problem: find k cycles all starting at a designated location such that each edge is traversed by at least one cycle. The goal is to minimize the cost of the most expensive cycle.
• Rural postman problem: Given is also a subset of the edges. Find the cheapest Hamiltonian cycle containing each of these edges (and possibly others). This is a special case of the minimum general routing problem which specifies precisely which vertices the cycle must contain.

See also

• Travelling salesman problem

References

1. ^ ""Chinese Postman Problem"". http://www.nist.gov/dads/HTML/chinesePostman.html. 
2. ^ J. Edmonds and E.L. Johnson, Matching Euler tours and the Chinese postman problem, Math. Program. (1973).
3. ^ Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. "A compendium of NP optimization problems". KTH NADA, Stockholm. http://www.nada.kth.se/~viggo/problemlist/compendium.html. Retrieved 2008-10-22. 

External links

• Chinese Postman Problem