Week 8. Structural Correspondence between Hamming Steiner Trees and Vertex Cover.

This week I proved a structural correspondence between vertex covers $4$-regular graphs and optimal Hamming Steiner trees of of the point configuration of the characteristic vectors of the edges. This structural result immediately implies the best known hardness of approximation factor for the Hamming and Rectilinear Steiner tree problems.

In addition, I proved APX-hardness of the Discrete $\ell_p$ Steiner tree problem for each $p \in \{0\} \cup [1, \infty) \cup \{\infty\}$.

At the end of the week, I gave a final presentation of my summer research to the DIMACS REU program. The slides are attached.