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

Abstract. 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. In the problem Formula: see text-Tour defined within this model, the objective is to find a shortest tour that comes within a distance of Formula: see text of every point on every edge. This problem was introduced in the predecessor to this article and shown to be essentially equivalent to the Chinese Postman problem for Formula: see text, to the graphic Travel Salesman Problem (TSP) for Formula: see text, and close to first vertex cover and then dominating set for even larger Formula: see text. 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 Formula: see text, the problem Formula: see text-Tour is APX-hard, while for every fixed Formula: see text, the problem has no polynomial-time Formula: see text-approximation unless Formula: see text. Our techniques also yield the new result that TSP remains APX-hard on cubic (and even cubic bipartite) graphs. (2) For every fixed Formula: see text, the problem Formula: see text-Tour is fixed-parameter tractable (FPT) when parameterized by the length of a shortest tour, while it is W2-hard for every fixed Formula: see text and para-NP-hard for Formula: see text being part of the input. On the other hand, if Formula: see text is considered to be part of the input, then an interesting nontrivial phenomenon occurs when Formula: see text is a constant fraction of the number of vertices: (3) If Formula: see text is part of the input, then the problem can be solved in time Formula: see text, where Formula: see text; however, assuming the exponential-time hypothesis (ETH), there is no algorithm that solves the problem and runs in time Formula: see text.