Anonymous Refugee Housing with Upper-Bounds
share
Knop and Schierreich [AAMAS '23] recently introduced a novel model of refugee housing and specifically asked for the computational complexity picture of the following variant. Given a topology modelled as an undirected graph, a set of inhabitants, a number of refugees R, an assignment of inhabitants to houses of the topology, and an upper-bound for every inhabitant, find a set π of unoccupied houses of size R intended such that the number of refugees in the neighbourhood of every inhabitant is at most its upper-bound. If such a set π exists, we say that the instance admits an inhabitant-respecting housing. In this paper, we show that the existence of inhabitant-respecting housing is not guaranteed even under several further restrictions of the upper-bounds. Then, we focus on the computational complexity of deciding whether inhabitant-respecting housing exists. To this end, we provide tractable algorithms for several restrictions of the topology. We complement these results with appropriate hardness results and running-time lower-bounds. Furthermore, we introduce a relaxed (or approximate) version of the inhabitant-respecting housing, where we allow at most t upper-bounds to be exceeded.
READ FULL TEXT