From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity

A well-studied continuous model of graphs considers each edge as a continuous unit-length interval of points. In the problem $δ$-Tour defined within this model, the objective to find a shortest tour that comes within a distance of $δ$ of every point on every edge. This parameterized problem was introduced in the predecessor to this article and shown to be essentially equivalent to the Chinese Postman problem for $δ= 0$, to the graphic Travel Salesman Problem (TSP) for $δ= 1/2$, and close to first Vertex Cover and then Dominating Set for even larger $δ$. Moreover, approximation algorithms for multiple parameter ranges were provided. In this article, we provide complementing inapproximability bounds and examine the fixed-parameter tractability of the problem. On the one hand, we show the following: (1) For every fixed $0 < δ< 3/2$, the problem $δ$-Tour is APX-hard, while for every fixed $δ\geq 3/2$, the problem has no polynomial-time $o(\log{n})$-approximation unless P = NP. Our techniques also yield the new result that TSP remains APX-hard on cubic (and even cubic bipartite) graphs. (2) For every fixed $0 < δ< 3/2$, the problem $δ$-Tour is fixed-parameter tractable (FPT) when parameterized by the length of a shortest tour, while it is W[2]-hard for every fixed $δ\geq 3/2$ and para-NP-hard for $δ$ being part of the input. On the other hand, if $δ$ is considered to be part of the input, then an interesting nontrivial phenomenon occurs 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 = \lceil n/δ\rceil$; 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)}$.