Week 2. Hardness of Approximating Euclidean Steiner trees.

In 1977, Garey proved that the Euclidean Steiner tree problem is $NP$-hard in the plane . Since 2-dimensional Euclidean spaces can be embedded in higher dimensional space, this immediately implies that the Euclidean Steiner tree problem is $NP$-hard in $\mathbb{R}^d$ for any $d$.

As a result, it is natural to wonder whether it is possible to compute approximately optimal Euclidean Steiner trees in polynomial time, for any approximate factor. Indeed, for a fixed dimension $d$, there exists a polynomial time $(1+ \epsilon)$-approximation algorithm for any $\epsilon$ as a result of a landmark 1998 paper of Arora.

What about when the dimension $d$ is a function of the number of points, $n$? In that case, the question remains open and is the target of our summer's work. We suspect that the problem is $APX$-hard in that case, that is, there exists some $\epsilon$ such that it is $NP$-hard to find $(1 + \epsilon)$-approximate solutions.

Indeed, a 1997 paper of Trevisan shows that the Steiner tree problem is hard to approximate, Max $SNP$-hard, for $n$ points in $n$-dimensional space in the $\ell_1$-metric. In Wareham's 1993 Master's thesis , they show that the Hamming Steiner tree problem is also Max $SNP$-hard.

As a first step toward the Euclidean problem, we devised a new proof of the Hamming Steiner tree problem being $APX$-hard using a reduction from the Vertex Cover problem on graphs. In particular, the Vertex Cover hardness is a 2019 result of Austrin and Aleksa, hopefully yielding more flexibility in our proof than that enjoyed by previous researchers studying the Euclidean problem. The idea is that similar methods should work in the Euclidean setting.