Heuristic/approximation solutions to Route Inspection/Chinese Postman problem

The Chinese Postman Problem or Route Inspection Problem on a graph $$G$$, finds a single path that traverses every edge of $$G$$ with the minimal possible number of edge repetitions.

The trivial solutions are when $$G$$ has no vertex of odd degree, or when $$G$$ has exactly two vertices of odd degree. In these cases, there exist an Eulerian Circuit or an Eulerian Path respectively, i.e., a single path that traverses every edge without repetitions. When $$G$$ has more than two odd-degree vertices, a solution can be obtained using Perfect Weight Matching, however, this is costly; as we require to compute a shortest-path-length distance matrix between every odd-degree vertex, as well as solve the matching subproblem. This makes it unpractical for massive graphs (e.g., if a graph has a million nodes, storing a distance matrix into RAM becomes hard).

Are there any well-known approximate/heuristic strategies to find a single path that traverses every edge without having to compute shortest-path distances? Ideally, in linear time (with respect to edges).

1 Answer

I don't know what approximation factor would be ok for you, but here is a simple 2-approximation algorithm that works in $$O(|V|+|E|)$$ assuming the graph is unweighted:

1. Calculate any spanning tree, substitute each edge by a pair of arcs directed in opposite directions and construct Eulerian tour $$T$$.
2. Optional: optimize the distances on the Eulerian tour using a single BFS started from all odd vertices simultaneously.
3. There are two ways to connect pair odd-degree vertices using $$T$$, e.g. in a cycle A-B-C-D-A you have either A-B, C-D or B-C, D-A. The sum of the two is twice the weight of the spanning tree, so one of them is at most the weight of one spanning tree.
4. Form $$G'$$ by connecting odd-degree vertices using $$T$$ and cheaper of the two ways from previous point.
5. Find the Eulerian tour in $$G'$$.

This algorithm is a 2-approximation, because the const of the spanning tree is certainly smaller than the cost of the whole tour.

I hope this helps $$\ddot\smile$$