Approximation and Hardness of Polychromatic TSP

Thomas Schibler, Subhash Suri, Jie Xue · 2025

Read Approximation and Hardness of Polychromatic TSP by Thomas Schibler, Subhash Suri, Jie Xue (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04974.txt.

Introduction

Thomas Schibler, Subhash Suri, and Jie Xue introduce the polychromatic traveling salesman problem. Their 2025 paper defines a graph whose vertices split into equal sized color classes. The goal is the shortest cycle that visits every vertex once while cycling through the color classes in a fixed order. The problem generalizes both the bipartite version and the classic traveling salesman problem.

For the metric case, the team gives a polynomial time approximation algorithm with a factor just under three. On the other side, they show the Euclidean version in the plane is APX-hard. That result rules out a fully efficient approximation scheme for it, unless a famous open question in computing resolves the other way.

Catalog record

CREATORThomas Schibler, Subhash Suri, Jie Xue
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-04974

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Approximation and Hardness of Polychromatic TSP Thomas Schibler, Subhash Suri, Jie Xue Abstract We introduce the Polychromatic Traveling Salesman Problem (PCTSP), where the input is an edge weighted graph whose vertices are partitioned into k k equal-sized color classes, and the goal is to find a minimum-length Hamiltonian cycle that visits the classes in a fixed cyclic order. This generalizes the Bipartite TSP (when k = 2 k=2 ) and the classical TSP (when k = n k=n ). We give a polynomial-time ( 3 − 2 ⋅ 10 − 36 ) (3-2\cdot 10^{-36}) -approximation algorithm for metric PCTSP. Complementing this, we show that Euclidean PCTSP is APX-hard even in ℝ 2 \mathbb{R}^{2} , ruling out the existence of a PTAS unless P = NP. 1 Introduction The classic Traveling Salesman Problem (TSP) takes an edge-weighted graph G as input and aims to find a minimum-weight Hamiltonian cycle in G (which by definition is a simple cycle that visits all vertices of G ). As one of the most fundamental algorithmic problems, TSP has stood as a testing ground for algorithmic developments in the theory community since its introduction as one of Karp’s original NP-Complete problems. In 1976, Christofides showed a 1.5-approximation for any metric graph G , and this bound resisted progress for decades until Karlin et al. [ 6 ] improved the bound (slightly) to 1.5-10^{-36} , which remains the best known. In the case that G contains only edge weights 1 and 2, Papadimitriou and Yannakakis obtained a better approximation ratio of 7/6, and showed that even this restricted case is APX-Hard, and thus does not admit a PTAS unless P=NP [ 8 ] . However, if the edge weights correspond to the Euclidean distances between points in some fixed \mathbb{R}^{d} , then a PTAS is known from the celebrated work of Arora [ 2 ] and Mitchell. In this paper, we consider a colored version of TSP, called polychromatic TSP (PCTSP), in which the vertices of G are partitioned into color classes of the same size and the goal is to find a TSP tour that repeatedly visits the color classes in a consistent order. Formally, a polychromatic graph consists of a graph G together with a partition \mathcal{P}=\{V_{1},\cdots,V_{k}\} of V(G) into subsets (called color classes ) of equal size (i.e., |V_{1}|=\cdots=|V_{k}| ) and a weight function w:E(G)\rightarrow\mathbb{R}_{\geq 0} . Let (G,\mathcal{P},w) be a polychromatic graph with |V(G)|=n and |\mathcal{P}|=k . The weight of a path/cycle \pi in G , denoted by w(\pi) , is the sum of the weights of the edges in \pi under the weight function w . For a permutation \sigma=(\sigma(0),\sigma(1),\dots,\sigma(k-1)) of [k]=\{1,\cdots,k\} , we say a cycle C in G is a \sigma -cycle if it can be written as C=(v_{0},v_{1},\cdots,v_{r}) where v_{r}=v_{0} such that v_{i}\in V_{\sigma(i\text{ mod }k)} for all i\in\{0\}\cup[r] ; the weight of C is equal to \sum_{i=1}^{n}w((v_{i-1},v_{i})) . Note that the length of a \sigma -cycle is always a multiple of k . Intuitively, a \sigma -cycle repeatedly visits the color classes of G in the order specified by \sigma . The goal of PCTSP is to find a minimum-weight Hamiltonian cycle in G that is a \sigma -cycle for some permutation \sigma of [k] . Clearly, when k=n , PCTSP is exactly the classic TSP. As such, PCTSP is a generalization of TSP and is thus NP-hard even when G is a metric graph. The main focus of this paper is to study the approximability of PCTSP in metric graphs, and more specifically, Euclidean graphs in a fixed dimension. We remark that PCTSP is a natural extension of Bipartite TSP, where a tour must alternate between red and blue nodes. This problem has long been studied in the robotics literature as an appropriate model for “pick and place” route planning [ 1 , 4 , 9 ] . (In this setting, a robot with unit capacity must move objects from a set of sources to a set of destinations, necessitating a route that alternates between the two node types.) For metric graphs, Anily and Hassin gave a 2.5 -approximation [ 1 ] , and Chalasani et al. [ 4 ] later improved the ratio to 2 . Lastly, many other lines of research consider chromatic variants of the TSP. For example, Dross et al. [ 5 ] give a Gap-ETH tight approximation scheme for the bicolored noncrossing Euclidean TSP, where the goal is to find a separate tour for the points of each color, such that the two do not intersect in \mathbb{R}^{2} . Baligács et al. give a constant factor approximation for the 3 -color version [ 3 ] . Other settings involve multiple salesman that can only visit given subsets of the colors, or seek the shortest cycle that visits each color once. In contrast, we aim for a single polychromatic tour that visits every node of G while cycling through a large number of colors. 1.1 Main results We initiate the study of metric PCTSP and Euclidean PCTSP in a fixed dimension. Our first result is a polynomial-time constant-approximation algorithm for PCTSP in metric graphs. Theorem 1.1 . There is a polynomial-time (3-2\cdot 10^{-36}) -approximation algorithm for metric PCTSP. To complement the above algorithmic result, we rule out the existence of (Q)PTASes for metric PCTSP and even Euclidean PCTSP, by proving the following APX-hardness result. Theorem 1.2 . Euclidean PCTSP in \mathbb{R}^{2} does not admit a PTAS unless P=NP. In particular, Euclidean PCTSP is APX-Hard. Organization. The rest of the paper is organized as follows. In Section 2 , we give the basic notions and preliminaries that are required for our results. Section 3 presents our approximation algorithm for metric PCTSP, and Section 4 presents our hardness result for Euclidean PCTSP. 2 Preliminaries For a graph G , we use V(G) and E(G) to denote the vertex set and edge set of G , respectively. For V\subseteq V(G) , we denote by G[V] the graph induced in G by V . Let (G,\mathcal{P},w) be a polychromatic graph where \mathcal{P}=\{V_{1},\dots,V_{k}\} . We call a cycle in G a polychromatic cycle in (G,\mathcal{P},w) if it is a \sigma -cycle for some permutation of [k] . We denote by \mathcal{H}_{G} the set of all Hamiltonian \sigma -cycles of G : \mathcal{H}_{G}=\{\pi:\text{$\pi$ is a polychromatic cycle and }V(\pi)=V(G)\} . In metric PCTSP, we are given a polychromatic graph (G,\mathcal{P},w) such that G is complete and w((v,v^{\prime}))\leq w((v,v^{\prime\prime}))+w((v^{\prime\prime},v^{\prime})) for all v,v^{\prime},v^{\prime\prime}\in V(G) . We are to compute \arg\min_{\pi\in\mathcal{H}_{G}}{w(\pi)} . In Euclidean PCTSP, the input is (P,\mathcal{P}) for a set of points P\subset\mathbb{R}^{d} , and partition of the points \mathcal{P}=\{P_{1},\cdots,P_{k}\} . The task is to solve metric PCTSP on input (G,\mathcal{P^{\prime}},w) , where G is the complete graph with vertices V(G)=\{v_{p}:p\in P\} , \mathcal{P^{\prime}}=\{P_{1}^{\prime},\cdots,P_{k}^{\prime}\} s.t. P_{i}^{\prime}=\{v_{p}:p\in P_{i}\} for all 1\leq i\leq k , and w((v_{p},v_{p^{\prime}}))=||p-p^{\prime}||_{2} . ||\cdot||_{2} denotes the Euclidean norm. For convenience, we similarly refer to a cycle of the points \pi=(p_{0},\cdots,p_{r}) where p_{r}=p_{0} as a \sigma -cycle if p_{i}\in P_{\sigma(i\text{ mod }k)} for all i\in\{0\}\cup[r] . The length of \pi is ||\pi||=\sum_{i\in[r]}||p_{i}-p_{i+1}||_{2} . Finally, we use the term \sigma -tour to mean a Hamiltonian \sigma -cycle. 3 Constant approximation for metric PCTSP In this section, we give

Read the complete text