2026-07-18T11:16:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22158 2024-12-04T06:53:44Z ddc:004 open_access

From Chinese Postman to Salesman and Beyond: Shortest Tour δ-Covering All Points on All Edges Frei, Fabian Ghazy, Ahmed Hartmann, Tim A. Hörsch, Florian Marx, Dániel Chinese Postman Problem Traveling Salesman Problem Continuous Graphs Approximation Algorithms Inapproximability Parameterized Complexity 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. On the one hand, we first 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. Our techniques also yield a new APX-hardness result for graphic TSP on cubic bipartite graphs. When parameterizing by the length of a shortest tour, 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 length of a shortest tour, 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fabian Frei and Ahmed Ghazy and Tim A. Hartmann and Florian Hörsch and Dániel Marx 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.31 urn:nbn:de:0030-drops-221582 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.31 eng https://creativecommons.org/licenses/by/4.0/legalcode