{"id":"arxiv/2605.04715","url":"https://arxiv.org/abs/2605.04715","tags":["cs.CG","cs.CC","math.OC"],"score":0,"title":"On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces","domain":"cs.CG","source":"arxiv","authors":["Michael T. M. Emmerich","Ksenia Pereverdieva","André Deutz"],"reviews":0,"subject":"cs.CG","summary":"We study the computational complexity of exact cardinality-constrained minimum Riesz $s$-energy subset selection in finite metric spaces: given $n$ points, select $k<n$ points of minimum Riesz $s$-energy. The objective sums inverse-power pair interactions and therefore promotes well-separated subsets; as $s$ becomes large, it increasingly approaches a bottleneck criterion governed by the closest selected pair, linking it to minimum pairwise distance (MPD). Building on the general-metric NP-hardness result of Pereverdieva et al. (2025), we prove that NP-hardness persists for point sets in the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-06","reactions":{}}