<p>It is NP-hard, here's a proof.</p>
<p>In [1], it is shown that the Hamiltonian path problem is NP-hard on induced subgraphs of the infinite grid (i.e. graphs that are defined by taking a set of integer points in 2D and connecting two points if their distance is 1).</p>
<p>From this, it follows that the 2D TSP with the Manhattan metric (i.e. <span class="math-container">$dist = |x_1-x_2|+|y_1-y_2|$</span>) is NP-hard, as such graph has a Hamiltonian path if and only if we have such tour with cost <span class="math-container">$n-1$</span>.</p>
<p>Now, to reduce the Manhattan metric to the max metric, we can simply use the mapping <span class="math-container">$(x,y) \mapsto (x+y,x-y)$</span>. In particular, it holds that <span class="math-container">$|x_1-x_2|+|y_1-y_2| = max(|x_1+y_1-x_2-y_2|, |x_1-y_1-x_2+y_2|)$</span>. This finishes the reduction.</p>
<p>[1] &quot;Hamilton Paths in Grid Graphs&quot; Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter, SICOMP, 1982, <a href="https://epubs.siam.org/doi/abs/10.1137/0211056" rel="nofollow noreferrer">https://epubs.siam.org/doi/abs/10.1137/0211056</a></p>

CC BY-SA 4.0
2024-06-22T17:08:04.363Z
2024-06-22T17:08:04.363Z
Laakeri
<p>I know that it is not too difficult to construct a metric to show that the metric TSP is NP-hard. The typical example is (1,2)-TSP.
I also know that Papadimitriou has shown that <a href="https://doi.org/10.1016/0304-3975(77)90012-3" rel="nofollow noreferrer">Euclidean TSP is NP-hard</a>. But I could not find anything about the hardness of the (2D) TSP with the maximum metric. Concretely, the problem is as follows:</p>
<p>Given a set of points <span class="math-container">$P \subset \mathbb{R}^2$</span>, find a tour <span class="math-container">$T = ((x_1, y_1), \dots, (x_{|P|}, y_{|P|}))$</span> that contains each point <span class="math-container">$p \in P$</span> exactly once such that the tour cost
<span class="math-container">$$
\sum_{i=1}^{|P|-1} \max \{ |x_i - x_{i+1}|, |y_i - y_{i+1}| \}
$$</span>
is minimized.</p>
<p>Is this problem NP-hard?</p>

<cc.complexity-theory><np-hardness><tsp><metrics>
Hardness of the Metric TSP for the Maximum Metric
jfriemel
# Hardness of the Metric TSP for the Maximum Metric

(Asked by: username_0 on 2024-06-21)

I know that it is not too difficult to construct a metric to show that the metric TSP is NP-hard. The typical example is (1,2)-TSP.
I also know that Papadimitriou has shown that [Euclidean TSP is NP-hard](https://doi.org/10.1016/0304-3975(77)90012-3). But I could not find anything about the hardness of the (2D) TSP with the maximum metric. Concretely, the problem is as follows:

Given a set of points $P \subset \mathbb{R}^2$, find a tour $T = ((x\_1, y\_1), \dots, (x\_{|P|}, y\_{|P|}))$ that contains each point $p \in P$ exactly once such that the tour cost
$$
\sum\_{i=1}^{|P|-1} \max \{ |x\_i - x\_{i+1}|, |y\_i - y\_{i+1}| \}
$$
is minimized.

Is this problem NP-hard?

**Tags:** cc.complexity-theory, np-hardness, tsp, metrics

---

## 1 answers

### Answer by username_1 on 2024-06-22. Score: 2 | Accepted answer

It is NP-hard, here's a proof.

In [1], it is shown that the Hamiltonian path problem is NP-hard on induced subgraphs of the infinite grid (i.e. graphs that are defined by taking a set of integer points in 2D and connecting two points if their distance is 1).

From this, it follows that the 2D TSP with the Manhattan metric (i.e. $dist = |x\_1-x\_2|+|y\_1-y\_2|$) is NP-hard, as such graph has a Hamiltonian path if and only if we have such tour with cost $n-1$.

Now, to reduce the Manhattan metric to the max metric, we can simply use the mapping $(x,y) \mapsto (x+y,x-y)$. In particular, it holds that $|x\_1-x\_2|+|y\_1-y\_2| = max(|x\_1+y\_1-x\_2-y\_2|, |x\_1-y\_1-x\_2+y\_2|)$. This finishes the reduction.

[1] "Hamilton Paths in Grid Graphs" Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter, SICOMP, 1982, <https://epubs.siam.org/doi/abs/10.1137/0211056>


---

