From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
SIAM Journal on Discrete Mathematics · 30.09.2026 · 40 (3) · 1066-1106
DOI: 10.1137/25m1736402 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 20.07.2026. Verfasst von Fabian Frei und 4 weiteren Autor:innen. Die Arbeit nennt 21 Literaturangaben. Gefördert von: Swiss National Science Foundation.
Abstract (Originalsprache)
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 W[2]-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].
Förderung
- Swiss National Science Foundation
Zitieren
APA
Frei, F., Ghazy, A., Hartmann, T. A., Hörsch, F., & Marx, D. (2026). From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity. SIAM Journal on Discrete Mathematics, 40(3), 1066-1106. https://doi.org/10.1137/25m1736402
Vancouver
Frei F, Ghazy A, Hartmann TA, Hörsch F, Marx D. From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity. SIAM Journal on Discrete Mathematics. 2026;40(3):1066-1106. doi:10.1137/25m1736402
BibTeX
@article{Frei2026,
author = {Frei, Fabian and Ghazy, Ahmed and Hartmann, Tim A. and Hörsch, Florian and Marx, Dániel},
title = {From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {3},
pages = {1066--1106},
doi = {10.1137/25m1736402}
}
EUVIMED