Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard

Michael T. M. Emmerich, Ksenia Pereverdieva, André H. Deutz

arXivarxiv/2604.05495Apr 7, 2026cs.CGscore 0

The Solow--Polasky diversity indicator (or magnitude) is a classical measure of diversity based on pairwise distances. It has applications in ecology, conservation planning, and, more recently, in algorithmic subset selection and diversity optimization. In this note, we investigate the computational complexity of selecting a subset of fixed cardinality from a finite set so as to maximize the Solow--Polasky diversity value. We prove that this problem is NP-hard in general metric spaces. The reduction is from the classical Independent Set problem and uses a simple metric construction…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2604.05495
curl -X POST /api/v1/records/arxiv/2604.05495/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.05495/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'