Fixed-dimensional hardness conjecture for MAX-EMST-ratio

For a point set in Euclidean space, the kk-MAX-EMST-ratio problem restricts the input to kk dimensions. Fixed-dimensional hardness conjecture. The kk-MAX-EMST-ratio problem for k{2,3}k\in\{2,3\} is NP-hard.

The unrestricted MAX-EMST-ratio problem is established to be NP-hard, while hardness in the specific practical dimensions 22 and 33 remains conjectural.

Sources & referencesView supporting material

Primary source

Afrouz Jabal Ameli, Faezeh Motiei and Morteza Saghafian, “On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum”, arXiv:2409.11079 (2025).

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.