Local stability of kidney exchanges with length-2 cycles

Kidney Exchange Programs (KEP) address the challenge of optimally assigning compatible kidney donors to patients who have willing but incompatible donors. In a KEP, incompatible donor-recipient pairs can "swap" donors with other pairs to create compatible matches. The swaps can involve multiple pairs in cyclic exchanges. The goal is to maximize the number of matches under various constraints, e.g., an upper bound on the cycle length or a stability requirement.
Here, we restrict our attention to cycles of length 2 and to the case where each recipient expresses preferences among its compatible donors. This is the setting of the classical Stable Roommates Problem (SRP). It gives rise to a graph model where vertices represent recipient-donor pairs and edges represent compatibilities. A matching M is called stable when it has no blocking pair, meaning a pair of vertices that would prefer to be matched together rather than to their current mates in M. Determining whether a stable matching exists for an instance of SRP, and producing one if it does, can be done in polynomial time.
Baratto et al. (2024) recently introduced a new concept called local stability (or L-stability). A matching M is L-stable if no blocking pair intersects M. We present several structural results on L-stable matchings, as well as a strong property of such matchings with respect to stable partitions. From these results, we derive a polynomial-time algorithm for computing an L-stable matching of maximum size.