{"id":"arxiv/2604.19484","url":"https://arxiv.org/abs/2604.19484","tags":["cs.CG","cs.CC","math.OC"],"score":0,"title":"Maximum Solow--Polasky Diversity Subset Selection Is NP-hard Even in the Euclidean Plane","domain":"cs.CG","source":"arxiv","authors":["Michael T. M. Emmerich","Ksenia Pereverdieva","André H. Deutz"],"reviews":0,"subject":"cs.CG","summary":"We prove that, for every fixed $θ_0>0$, selecting a subset of prescribed cardinality that maximizes the Solow--Polasky diversity indicator is NP-hard for finite point sets in $\\mathbb{R}^2$ with the Euclidean metric, and therefore also for finite point sets in $\\mathbb{R}^d$ for every fixed dimension $d \\ge 2$. This strictly strengthens our earlier NP-hardness result for general metric spaces by showing that hardness persists under the severe geometric restriction to the Euclidean plane. At the same time, the Euclidean proof technique is different from the conceptually easier earlier…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-21","reactions":{}}