Heuristic/approximation solutions to Route Inspection/Chinese Postman problem

Question

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

Answer 1

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$