Week 7. Better Inapproximability Bounds for Hamming Steiner Trees.

This week I attempted to remove my dependence on making the graphs triangle-free. At first, I tried to do this by showing that there are triangle-free graphs with the same hardness of approximability of Vertex Cover with the same ratio of edges to size of Vertex Cover. However, by the end of the week I realized that triangle-free is actually unnecessary—the $4$-regularity of the graphs was sufficient. Hence, I managed to improve the best known inapproximability bound. This new result has further applications to a discrete variant of the Metric Space Steiner Tree problem.