Euclidean 3D Stable Roommates is NP-hard.
Jiehua Chen, Sanjukta Roy · arXiv (Cornell University) · 2021
We establish NP-completeness for the Euclidean 3D Stable Roommates problem, which asks whether a given set $V$ of $3n$ points from the Euclidean space can be partitioned into $n$ disjoint (unordered) triples $\Pi=\{V_1,\dots,V_n\}$ such that $\Pi$ is stable. Here, stability means that no three points $x,y,z\in V$ are blocking $\Pi$, and $x,y,z\in V$ are said to be blocking $\Pi$ if the following is satisfied: -- $\delta(x,y)+\delta(x,z) < \delta(x,x_1)+\delta(x,x_2)$, -- $\delta(y,x)+\delta(y,z) < \delta(y,y_1)+\delta(y, y_2)$, and -- $\delta(z,x)+\delta(z,y) < \delta(z,z_1)+\delta(z,z_2)$, where $\{x,x_1,x_2\}, \{y,y_1,y_2\}, \{z,z_1,z_2\}\in \Pi$, and $\delta(a,b)$ denotes the Euclidean distance between $a$ and $b$.