- On Inapproximability of Steiner Tree Computation in Hamming and Rectilinear metrics
- Project Year:
2022
- REU Student (s):
Henry Fleischmann | University of Michigan-Ann Arbor MI
- Student 1 Institution:
University of Michigan-Ann Arbor
- Project Mentor:
Karthik Srikanta
- Project Mentor Area:
Computer Science
- Project Abstract:
We consider the Steiner tree problem in Hamming space. While this problem is known to be APX-hard, no hardness of approximation factor is known. We show that the Hamming Steiner tree problem is NP-hard to approximate within a factor of 104. In showing this, we derive a structural correspondence between vertex covers of 4-regular graphs and optimal Hamming Steiner trees of particular point configurations in Hamming space. As a corollary of our results, we show that the Rectilinear Steiner tree problem is NP-hard to approximate within a factor of 104. We also show analagous results for discrete variants of the Steiner tree problem. That is, the Hamming and Rectilinear Discrete Steiner tree problems are NP-hard to approximate within a factor of 104.
