Star embedding conjecture for Euclidean Steiner trees
Star embedding conjecture for Euclidean Steiner trees
Let be a graph with 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 edges, the embedding of the star graph on 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.