1
$\begingroup$

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

$\endgroup$
1
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.