It is known that a stable matching may not exist under the HRS setting and that deciding whether an HRS instance admits a stable matching is NP-hard under severe restrictions. We provide an alternate NP-hardness proof for the decision problem which imposes a severe restriction on the number of neighbours of non-unit sized agents. We show that for generalized master list setting, a stable matching always exists and can be efficiently computed. In this talk, I will present this algorithmic result.

Given the non-existence and intractability of the decision problem for stability, we explore a variation of stability, which we term occupancy-based stability. This notion was defined by McDermid and Manlove (J. of Comb. Opt. 2010) but remained unexplored to the best of our knowledge. We show that every HRS instance admits an occupancy-stable matching. We further show that computing a maximum-size occupancy-stable matching is NP-hard. We complement our hardness result by providing an approximation algorithm with a guarantee strictly better than 3 for the max-size occupancy-stable matching problem. In this talk, I will present the existence and approximation guarantee.

This is a joint work with Haricharan Balasundaram, J. B. Krishnashree and Meghana Nasre and it appeared in the proceedings of FSTTCS 2025.