Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911571668631552 |
|---|---|
| author | Emmerich, Michael T. M. Pereverdieva, Ksenia Deutz, André H. |
| author_facet | Emmerich, Michael T. M. Pereverdieva, Ksenia Deutz, André H. |
| contents | 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 containing only two non-zero distance values. Importantly, the hardness result holds for every fixed kernel parameter $θ_0>0$; equivalently, by rescaling the metric, one may fix the parameter to $1$ without loss of generality. A central point is that this is not a boilerplate reduction: because the Solow--Polasky objective is defined through matrix inversion, it is a nontrivial nonlinear function of the distances. Accordingly, the proof requires a dedicated strict-monotonicity argument for the specific family of distance matrices arising in the reduction; this strict monotonicity is established here for that family, but it is not assumed to hold in full generality. We also explain how the proof connects to continuity and monotonicity considerations for diversity indicators. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_05495 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard Emmerich, Michael T. M. Pereverdieva, Ksenia Deutz, André H. Computational Geometry Computational Complexity Information Theory Optimization and Control 68Q17, 90C27, 05C69 F.2.2; F.1.3 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 containing only two non-zero distance values. Importantly, the hardness result holds for every fixed kernel parameter $θ_0>0$; equivalently, by rescaling the metric, one may fix the parameter to $1$ without loss of generality. A central point is that this is not a boilerplate reduction: because the Solow--Polasky objective is defined through matrix inversion, it is a nontrivial nonlinear function of the distances. Accordingly, the proof requires a dedicated strict-monotonicity argument for the specific family of distance matrices arising in the reduction; this strict monotonicity is established here for that family, but it is not assumed to hold in full generality. We also explain how the proof connects to continuity and monotonicity considerations for diversity indicators. |
| title | Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard |
| topic | Computational Geometry Computational Complexity Information Theory Optimization and Control 68Q17, 90C27, 05C69 F.2.2; F.1.3 |
| url | https://arxiv.org/abs/2604.05495 |