The Complexity of Minimum-Envy House Allocation Over Graphs

Palash Dey, Anubhav Dhar, Ashlesha Hota, Sudeshna Kolay · 2025

Read The Complexity of Minimum-Envy House Allocation Over Graphs by Palash Dey, Anubhav Dhar, Ashlesha Hota, Sudeshna Kolay (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00296.txt.

Description

Anubhav Dhar and co-authors present a 2025 algorithms paper on dividing houses among friends without breeding resentment. In their model, agents sit on a friendship graph and can only envy a neighbor. You resent a friend who got a house you like while you got none you like. Two goals follow: minimize the number of envious agents, then, among the least-envious splits, make the most agents happy.

The boundary between easy and hard turns out razor-thin. When each agent likes at most one house, both problems solve in polynomial time; allow two liked houses and both become NP-hard. For structured graphs, sparse ones or those with small separators or vertex covers, the authors design exact algorithms that beat brute force comfortably.

Catalog record

CREATORPalash Dey, Anubhav Dhar, Ashlesha Hota, Sudeshna Kolay
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE97 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-00296

Browse the full library · About the Tower of Babel