From Chinese Postman to Salesman and Beyond: Shortest Tour δ-Covering All Points on All Edges

Summary

A well-studied continuous model of graphs, introduced by Dearing and Francis [Transportation Science, 1974], considers each edge as a continuous unit-length interval of points. For δ >= 0, we introduce the problem δ-Tour, where the objective is to find the shortest tour that comes within a distance of δ of every point on every edge. It can be observed that 0-Tour is essentially equivalent to the Chinese Postman Problem, which is solvable in polynomial time. In contrast, 1/2-Tour is essentially equivalent to the graphic Traveling Salesman Problem (TSP), which is NP-hard but admits a constant-factor approximation in polynomial time. We investigate δ-Tour for other values of δ, noting that the problem's behavior and the insights required to understand it differ significantly across various δ regimes. First, we examine the approximability of the problem for every fixed δ > 0: (1) For every fixed 0 < δ < 3/2, the problem δ-Tour admits a constant-factor approximation and is APX-hard, while for every fixed δ >= 3/2, the problem admits an O(log n)-approximation in polynomial time and has no polynomial-time o(log n)-approximation, unless P = NP. When parameterizing by the minimum tour length, it is relatively easy to show that 3/2 is the threshold of fixed-parameter tractability: (2) For every fixed 0 < δ < 3/2, the problem δ-Tour is fixed-parameter tractable (FPT) when parameterized by the minimum tour length, while it is W[2]-hard for every fixed δ >= 3/2. On the other hand, if δ is considered to be part of the input, then an interesting nontrivial phenomenon appears when δ is a constant fraction of the number of vertices: (3) If δ is part of the input, then the problem can be solved in time f(k) n^O(k), where k = ⌈n/δ⌉; however, assuming the Exponential-Time Hypothesis (ETH), there is no algorithm that solves the problem and runs in time f(k) n^o(k/log k). Our techniques also yield APX-hardness as a new result for graphic TSP on cubic bipartite graphs.