Star embedding conjecture for Euclidean Steiner trees

Let GG be a graph with mm edges, and embed each edge by its characteristic vector, as in the Vertex Cover reduction discussed in the source. Consider the Euclidean Steiner tree of the resulting point configuration. Star embedding conjecture. Over all graphs with mm edges, the embedding of the star graph on mm edges has the minimum cost Steiner tree. The source presents this as a weaker version of the fixed-terminal simplex conjecture and as relevant to proving APX-hardness of Euclidean Steiner Tree. Its resolution is not stated.

Sources & referencesView supporting material

Primary source

Henry Fleischmann, Guillermo A. Gamboa Q., Karthik C. S., Josef Matějka and Jakub Petr, “On Steiner Trees of the Regular Simplex”, arXiv:2312.01252 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.