We investigate the Euclidean 𝖽-Dimensional Stable Roommates problem, which asks whether a given set V of 𝖽⋅n points from the 2-dimensional Euclidean space can be partitioned into n disjoint (unordered) subsets Π=$V1,…,Vn$with | V_i | = 𝖽foreachV_i \in \Pisuchthat\Pi$$ is {stable}. |
Here, stability means that no point subset W⊆V is blocking Π, and W is said to be blocking Π if $$ | W | = 𝖽suchthat\Sigma_{w’ \in W} \delta(w,w’) < \Sigma_{v \in \Pi(w)}\delta(w,v)holdsforeachpointw \in W,where\Pi(w)denotesthesubsetV_i \in \Piwhichcontainswand\delta(a,b)denotestheEuclideandistancebetweenpointsaandb.Complementingtheexistingknownpolynomial−timeresultfor𝖽 = 2,weshowthatsuchpolynomial−timealgorithmscannotexistforanyfixednumber𝖽 \ge 3unlessP=NP.Ourresultfor𝖽 = 3$$ answers a decade-long open question in the theory of Stable Matching and Hedonic Games [Iwama et al., 2007; Arkin et al., 2009; Vladimir G. Deineko and Gerhard J. Woeginger, 2013; Vladimir G. Deineko and Gerhard J. Woeginger, 2013; David F. Manlove, 2013]. |
====================================
The conference version and the long version of the paper can be found at ESA22 and on arXiv.