Ksenia Pereverdieva

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

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 Euclidean plane when $s$ is part of the input. In contrast, finite ultrametric spaces form an exact tractable regime: on rooted binary ultrametric trees with $n$ leaves, an optimal size-$k$ subset can be computed by dynamic programming in $O(nk^2)$ time. We also discuss the ordered one-dimensional Euclidean case, where the classical MPD objective admits simple dynamic programming, but the additive Riesz energy does not appear to allow the same state compression. Finally, we explain why one natural route to fixed-$s$ Euclidean hardness does not close: Fowler-style 3SAT gadgets, together with zeta-function bounds for far-field interactions, show why this approach still requires an exponent depending on $k$. Together, these results provide a compact complexity landscape for a natural diversity or dispersion objective, distinguishing Euclidean hardness, ultrametric tractability, and the ordered one-dimensional case.

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

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.

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

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 argument for arbitrary metric spaces, and that general metric-space construction does not directly translate to the Euclidean setting. In the earlier proof one can use an exact construction tailored to arbitrary metrics, essentially exploiting a two-distance structure. In contrast, such an exact realization is unavailable in fixed-dimensional Euclidean space, so the present reduction requires a genuinely geometric argument. Our Euclidean proof is based on two distance thresholds, which allow us to separate yes-instances from no-instances by robust inequalities rather than by the exact construction used in the general metric setting. The main technical ingredient is a bounded-box comparison lemma for the nonlinear objective $\mathbf{1}^{\top}Z^{-1}\mathbf{1}$, where $Z_{ij}=e^{-θ_0 d(x_i,x_j)}$. This lemma controls the effect of perturbations in the pairwise distances well enough to transfer the gap created by the reduction. The reduction is from \emph{Geometric Unit-Disk Independent Set}. We present the main argument in geometric form for finite subsets of $\mathbb{R}^2$, with an appendix supplying the bit-complexity details needed for polynomial-time reducibility.