# From Chinese Postman to Salesman and Beyond: Shortest Tour δ-Covering All Points on All Edges

conference contribution

posted on 2024-10-30, 16:50 authored by Fabian FreiFabian Frei, Ahmed GhazyAhmed Ghazy, Tim HartmannTim Hartmann, Florian HörschFlorian Hörsch, Dániel MarxDániel MarxA 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.
First, we 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.
When parameterizing by the minimum tour length, 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 minimum tour length, 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).
Our techniques also yield APX-hardness as a new result for graphic TSP on cubic bipartite graphs.

## History

## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

International Symposium on Algorithms and Computation (ISAAC)## BibTeX

@conference{Frei:Ghazy:Hartmann:Hörsch:Marx:2024, title = "From Chinese Postman to Salesman and Beyond: Shortest Tour δ-Covering All Points on All Edges", author = "Frei, Fabian" AND "Ghazy, Ahmed" AND "Hartmann, Tim A" AND "Hörsch, Florian" AND "Marx, Dániel", year = 2024, month = 10 }## Usage metrics

## Categories

No categories selected## Keywords

## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC