What question did this study set out to answer?

This research aims to explore the inapproximability bounds and fixed-parameter tractability of the continuous graph Tour problem.

July 23, 2026SIAM Journal on Discrete Mathematics0 citationsOpen Access

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

FFFabian FreiIIT@MIT AGAhmed GhazyHelmholtz Center for Information Security THTim A. HartmannHelmholtz Center for Information Security

Puntos clave

This research aims to explore the inapproximability bounds and fixed-parameter tractability of the continuous graph Tour problem.
Provides inapproximability results for the Tour problem under various parameter settings.
Examines fixed-parameter tractability based on the length of the shortest tour.
Identifies conditions under which the Traveling Salesman Problem is APX-hard.
Demonstrates that the Tour problem is APX-hard for fixed values and has no polynomial-time q-approximation unless certain complexity assumptions hold.
Establishes fixed-parameter tractability for the Tour problem based on the shortest tour length while noting W[2]-hardness for other parameters.
Shows that when the length is part of the input, the problem can be solved in exponential time under specific constraints.

Resumen

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.

Preguntar a la IA

Me gusta

Guardar

Ver artículo completo