arxiv: 2605.04715 · v1 · submitted 2026-05-06 · 💻 cs.CG · cs.CC· math.OC

Recognition: unknown

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces

Michael T. M. Emmerich , Ksenia Pereverdieva , Andr\'e Deutz

Authors on Pith no claims yet

Pith reviewed 2026-05-08 16:13 UTC · model grok-4.3

classification 💻 cs.CG cs.CCmath.OC

keywords Riesz s-energysubset selectionNP-hardnessultrametric spacesdynamic programmingEuclidean planeminimum pairwise distancecomputational complexity

0 comments

The pith

Minimum Riesz s-energy k-subset selection is NP-hard in the Euclidean plane but solvable exactly on ultrametric trees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines selecting exactly k points out of n to minimize the sum of inverse-power pairwise distances, an objective that favors well-separated configurations. It establishes that this remains NP-hard when the points lie in the Euclidean plane and the exponent s forms part of the input. By contrast, the same task becomes solvable in O(n k squared) time through dynamic programming once the metric is ultrametric and realized as a rooted binary tree. The contrast isolates how geometric structure controls computational difficulty for this dispersion criterion. The authors also note that standard gadget reductions fail to settle the fixed-s case in the plane because far-field interactions introduce k-dependent exponents.

Core claim

The central claim is that cardinality-constrained minimum Riesz s-energy subset selection is NP-hard for Euclidean points in the plane when s is part of the input, extending prior general-metric hardness, while the identical problem on rooted binary ultrametric trees with n leaves admits an exact O(n k squared) dynamic programming solution that recurses over subtrees while tracking the number of selected points.

What carries the argument

Dynamic programming recursion over subtrees of a rooted binary ultrametric tree that maintains states for the number of selected points in each subtree and accumulates the Riesz energy contributions.

If this is right

Exact optimal dispersion subsets can be computed without approximation whenever the input metric satisfies the ultrametric inequality on a binary tree.
Applications that select diverse points from hierarchical data structures become solvable to optimality in quadratic time.
The one-dimensional Euclidean line separates the bottleneck minimum-pairwise-distance objective, which admits simple dynamic programming, from the full additive Riesz energy, which does not.
Practical dispersion tasks in the plane must rely on heuristics or approximation schemes once s varies with the instance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The ultrametric tractability may extend to other hierarchical or tree-like distance structures common in clustering or phylogenetic data.
Resolving whether hardness persists for any fixed s would clarify the complexity of common choices such as inverse-square energy.
The geometric separation between plane and tree metrics suggests exploring approximation algorithms that exploit low doubling dimension or other intermediate properties.
Hybrid methods could combine the tree dynamic program on embedded hierarchies with local Euclidean adjustments for mixed data sets.

Load-bearing premise

The NP-hardness result in the Euclidean plane requires that the exponent s can be chosen as part of the input rather than fixed in advance.

What would settle it

Either an algorithm that solves minimum Riesz s-energy k-subset selection in polynomial time for points in the Euclidean plane with any fixed constant s, or a reduction establishing NP-hardness for some fixed s.

Figures

Figures reproduced from arXiv: 2605.04715 by Andr\'e Deutz, Ksenia Pereverdieva, Michael T. M. Emmerich.

**Figure 1.** Figure 1: Illustration of δmax and Dmin used in the GIS-to-RSSP reduction. The dotted circles indicate the threshold radius δ around p1 and p2. Here δmax is realized by the forbidden pair of maximum radius (p1, p5) lying just above the threshold, while Dmin is realized by the admissible pair with minimum radius (p2, p3) lying at or above the threshold. Choosing s so that k 2 D −s min < δ−s max ensures that one f… view at source ↗

**Figure 2.** Figure 2: An abstract ultrametric tree on six taxa with two cherries. The pairs view at source ↗

**Figure 3.** Figure 3: Boolean circuit gadget. Wire gadget. Crossover gadget. Clause gadget view at source ↗

**Figure 4.** Figure 4: Disk-based gadget layout in the Euclidean plane following the structure of Fowler, Paterson, and Tani view at source ↗

**Figure 5.** Figure 5: Packing of equal-radius discs in the Euclidean plane. Around a fixed selected disc, the number of non view at source ↗

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper maps NP-hardness for Riesz s-energy k-subset selection in the Euclidean plane when s varies, against an O(nk^2) DP that works exactly on ultrametric trees.

read the letter

The main point is that Riesz s-energy minimization for k-subsets stays NP-hard in the Euclidean plane as long as s is allowed to vary with the instance, while it becomes polynomial on ultrametric spaces thanks to a new dynamic program. What stands out is the extension of the 2025 general-metric hardness to Euclidean points and the O(nk^2) DP on rooted binary ultrametric trees. The DP exploits the fact that distances between points in different subtrees are constant, which simplifies the recurrence nicely. They also give a clear reason why standard 3SAT reductions don't yield fixed-s hardness without k-dependent exponents. The paper does a good job keeping the claims proportionate. It distinguishes the tractable ultrametric case from the hard Euclidean one without pretending to solve everything. The discussion of the ordered line case highlights why the energy version resists the compression that works for pure min-distance. Soft spots are small. The hardness for fixed s is left open, as the authors themselves note, and the 1D observation is more negative than positive. But the core results look supported by the reductions and recurrence given. No circularity or fitting issues. This work is aimed at computational geometers and optimization researchers who care about dispersion or diversity objectives. It helps decide when to use exact methods versus heuristics. I would bring it to a reading group if the group covers complexity in geometry. It deserves serious peer review because the results are concrete and the limitations are stated plainly.

Referee Report

0 major / 2 minor

Summary. The paper studies the complexity of exact minimum Riesz s-energy k-subset selection in finite metric spaces. It proves NP-hardness for Euclidean-plane instances when s is part of the input (via reduction from general-metric hardness), shows that the problem is solvable in O(n k^2) time by dynamic programming on rooted binary ultrametric trees, discusses why the ordered 1D Euclidean case does not admit the same compression as the minimum-pairwise-distance objective, and explains why Fowler-style 3SAT gadgets with zeta-function bounds fail to establish fixed-s Euclidean hardness independent of k.

Significance. If the stated reductions and DP recurrence hold, the work supplies a compact and useful complexity landscape for a natural dispersion objective, cleanly separating Euclidean hardness (with variable s) from ultrametric tractability. The explicit, self-contained DP and the transparent discussion of the fixed-s limitation are concrete strengths that strengthen the contribution.

minor comments (2)

§3 (ultrametric DP): the recurrence is stated for binary trees; a brief remark on whether the same O(n k^2) bound extends to general ultrametric spaces (or requires a different tree representation) would improve clarity.
The abstract and §4 note that fixed-s hardness remains open; a short sentence summarizing the precise obstruction (exponent depending on k) in the main text would help readers locate the limitation quickly.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment, accurate summary of the contributions, and recommendation to accept. The report correctly identifies the separation between Euclidean hardness (with variable s) and ultrametric tractability, as well as the discussion of fixed-s limitations.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper derives its core results through explicit reductions (general-metric NP-hardness extended to Euclidean plane with s as input) and a self-contained dynamic program (O(nk²) DP on binary ultrametric trees exploiting uniform cross terms). These steps rely on standard algorithmic constructions and complexity arguments rather than fitted parameters, self-definitional loops, or predictions that collapse to inputs. The cited prior result on general metrics provides background but is not load-bearing for the new Euclidean or ultrametric claims, which are independently verified within the manuscript. Limitations for fixed-s hardness are discussed transparently without circular justification.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard complexity-theoretic axioms and metric-space definitions; no free parameters are fitted and no new entities are postulated.

axioms (2)

standard math P ≠ NP for the purpose of hardness statements
Invoked implicitly in all NP-hardness claims.
domain assumption Ultrametric spaces satisfy the strong triangle inequality d(x,z) ≤ max(d(x,y), d(y,z))
Used to enable the tree DP structure.

pith-pipeline@v0.9.0 · 5601 in / 1283 out tokens · 29469 ms · 2026-05-08T16:13:27.161050+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

23 extracted references · 16 canonical work pages · 1 internal anchor

[1]

P. K. Agarwal, M. van Kreveld, and S. Suri. Label placement by maximum independent set in rectangles. Computational Geometry, 11(3–4):209–218, 1998

1998
[2]

P. K. Agarwal, M. Overmars, and M. Sharir, Computing maximally separated sets in the plane,SIAM Journal on Computing, 36(3):815–834, 2006

2006
[3]

S. Atta. Riesz Energy Minimization Facility Location Problem in the Plane: Complexity and a Polynomial-Time Approximation Scheme.Theoretical Computer Science, 1070:115833, 2026. doi:10.1016/j.tcs.2026.115833

work page doi:10.1016/j.tcs.2026.115833 2026
[4]

Unit disk graphs,

B. N. Clark, C. J. Colbourn, and D. S. Johnson, “Unit disk graphs,”Discrete Mathematics, 86(1–3):165–177, 1990

1990
[5]

S. V . Borodachov, D. P. Hardin, and E. B. Saff.Discrete Energy on Rectifiable Sets. Springer Monographs in Mathematics. Springer, New York, 2019. doi:10.1007/978-0-387-84808-0

work page doi:10.1007/978-0-387-84808-0 2019
[6]

Emmerich, M. (2026). Exact Dynamic Programming for Solow–Polasky Diversity Subset Selection on Lines and Staircases. arXiv:2604.26929

work page internal anchor Pith review Pith/arXiv arXiv 2026
[7]

Arenas, T

M. Arenas, T. C. Merkl, R. Pichler, and C. Riveros. Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue.Proceedings of the ACM on Management of Data, 2(5):215:1–215:26, 2024

2024
[8]

J. S. Brauchart and P. J. Grabner. Distributing many points on spheres: minimal energy and designs.Journal of Complexity, 31(3):293–326, 2015. doi:10.1016/j.jco.2015.02.001

work page doi:10.1016/j.jco.2015.02.001 2015
[9]

B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit disk graphs.Discrete Mathematics, 86(1–3):165–177, 1990

1990
[10]

M. T. M. Emmerich. Minimum Rieszs-Energy Subset Selection in Ordered Point Sets via Dynamic Program- ming. arXiv:2502.01163, 2025

work page arXiv 2025
[11]

G. N. Frederickson and D. B. Johnson. Generalized selection and ranking: Sorted matrices.SIAM Journal on Computing, 13(1):14–30, 1984. doi: 10.1137/0213002

work page doi:10.1137/0213002 1984
[12]

J. G. Falc ´on-Cardona, L. Uribe, and P. Rosas. Rieszs-Energy as a Diversity Indicator in Evolution- ary Multi-Objective Optimization.IEEE Transactions on Evolutionary Computation, early online, 2024. doi:10.1109/TEVC.2024.3405197

work page doi:10.1109/tevc.2024.3405197 2024
[13]

J. G. Falc ´on-Cardona, J. Ju´arez, L. A. M´arquez-Vega, and M. T. M. Emmerich. Fast High-Diversity Subset Se- lection for Multi-Objective Optimization by Rieszs-Energy.IEEE Transactions on Evolutionary Computation, early online, 2025. doi:10.1109/TEVC.2025.3570938

work page doi:10.1109/tevc.2025.3570938 2025
[14]

R. J. Fowler, M. S. Paterson, and S. L. Tanimoto. Optimal packing and covering in the plane are NP-complete. Information Processing Letters, 12(3):133–137, 1981

1981
[15]

Fejes T ´oth

L. Fejes T ´oth. ¨Uber die dichteste Kugellagerung.Mathematische Zeitschrift, 48:676–684, 1943

1943
[16]

J. B. Ghosh. Computational aspects of the maximum diversity problem.Operations Research Letters, 19(4):175– 181, 1996. doi:10.1016/0167-6377(96)00025-9

work page doi:10.1016/0167-6377(96)00025-9 1996
[17]

L. A. Glazko and M. Nei. Estimation of divergence times for major lineages of primate species.Molecular Biology and Evolution, 20(3):424–434, 2003. doi:10.1093/molbev/msg050

work page doi:10.1093/molbev/msg050 2003
[18]

Hartmann and M

K. Hartmann and M. Steel. Maximizing phylogenetic diversity in biodiversity conservation: greedy solutions to the Noah’s Ark problem.Systematic Biology, 55(4):644–651, 2006. doi:10.1080/10635150600873876

work page doi:10.1080/10635150600873876 2006
[19]

Manson, C

K. Manson, C. Semple, and M. Steel. Counting and optimising maximum phylogenetic diversity sets.Journal of Mathematical Biology, 85:11, 2022. doi:10.1007/s00285-022-01779-3

work page doi:10.1007/s00285-022-01779-3 2022
[20]

B. Q. Minh, S. Klaere, and A. von Haeseler. Phylogenetic Diversity within Seconds.Systematic Biology, 55(5):769–773, 2006. doi:10.1080/10635150600981604

work page doi:10.1080/10635150600981604 2006
[21]

Pereverdieva, A

K. Pereverdieva, A. Deutz, T. Ezendam, T. B ¨ack, H. Hofmeyer, and M. T. M. Emmerich. Comparative analysis of indicators for multi-objective diversity optimization. InEvolutionary Multi-Criterion Optimization, volume 15513 ofLecture Notes in Computer Science, pages 58–71. Springer, 2025. doi:10.1007/978-981-96-3538-2 5

work page doi:10.1007/978-981-96-3538-2 2025
[22]

S. S. Ravi, D. J. Rosenkrantz, and G. K. Tayi. Heuristic and special case algorithms for dispersion problems. Operations Research, 42(2):299–310, 1994. doi:10.1287/opre.42.2.299

work page doi:10.1287/opre.42.2.299 1994
[23]

Stivala, G

A. Stivala, G. Robins, Y . Kashima, and M. Kirley. Ultrametric distribution of culture vectors in an extended Axelrod model of cultural dissemination.Scientific Reports, 4:4870, 2014. doi:10.1038/srep04870. 15

work page doi:10.1038/srep04870 2014