Riesz Energy Subset Selection in the Euclidean Plane is NP-Hard: A Reduction from the Ising Model on Planar Cubic Graphs

Abstract

We prove that minimum Riesz $s$-energy subset selection in the Euclidean plane is NP-complete already for the fixed exponent $s=2$. To our knowledge, this is the first Euclidean hardness result for exact Riesz-energy subset selection in which both the ambient dimension and the exponent are fixed. The reduction uses Barahona's planar cubic Ising model with uniform field. A spin is encoded by one diagonal of a four-point square. Axis-aligned selector chains implement ferromagnetic consistency, while a $45^{\circ }$ terminal geometry yields an antiferromagnetic source interaction. Rational diagonal perturbations realize the magnetic field, and all remaining interactions are dominated by polynomial separation. Because $s=2$ and all coordinates are rational, every constructed energy and the decision threshold are rational exactly.

Keywords: Riesz energy, subset selection, NP-completeness, geometric optimization, planar cubic graphs, independent set, Ising model, computational geometry Update V3.0: Adversarial proof audit with Claude Fable 5 and augmented Git with lean proof support and audit result. Sharpened some constants. No fundamental changes or new results w.r.t. previous versions