Stable Matchings with Covering Constraints: A Complete Computational Trichotomy

Matthias Mnich, Ildikó SchlotterAlgorithmica 2020 · OpenReview

Abstract

Finding stable matchings that satisfy lower quotas is a critical problem in applications ranging from rural hospital staffing to school choice. While generally NP-hard, this paper provides a definitive map of the computational landscape using parameterized complexity. We establish a complete trichotomy, categorizing problem variants as polynomial-time solvable (P), fixed-parameter tractable (FPT), or fundamentally intractable (W[1]-hard).

Introduction

The classic Stable Marriage (SM) problem ensures that no pair of participants prefers each other over their assigned partners. However, real-world scenarios often impose "covering constraints" or lower quotas—for instance, ensuring a minimum number of residents are assigned to a rural hospital. When these constraints are introduced, a perfectly stable matching may not exist. The objective then becomes finding a matching that satisfies all lower quotas while minimizing the number of blocking pairs ($b$).

Methodology: Parameterized Complexity

Given that the general problem is NP-hard and difficult to approximate, the authors employ the framework of parameterized complexity. This approach investigates how the computational difficulty scales with specific problem parameters rather than just the total input size. The primary parameters considered include:

  • $b$: The number of allowed blocking pairs.
  • $|W^*|, |M^*|$: The number of "distinguished" women or men who must be matched.
  • $\Delta_W, \Delta_M$: The maximum length of preference lists for women and men.

The study utilizes hardness reductions from problems like Multicolored Clique to prove intractability and develops novel FPT algorithms using weighted bipartite matching and augmenting paths for more tractable cases.

The Computational Trichotomy

The core contribution of this research is a complete classification of the problem's complexity across various parameter combinations. This "trichotomy" identifies the boundaries between efficiency and intractability.

Summary of complexity results for Stable Marriage with Covering constraints (SMC) across various parameter combinations.

As shown in the summary table above, the results fall into three distinct categories:

  1. Polynomial Time (P): The problem is efficiently solvable if preference lists are very short ($\Delta \le 2$) on both sides or if no covering constraints exist.
  2. Fixed-Parameter Tractable (FPT): While NP-hard, the problem is solvable in time that scales well with parameters like $|W^*| + |M^*|$, provided preference lists remain relatively short ($\Delta_W \le 2$).
  3. Intractable (W[1]-hard): The problem remains fundamentally difficult even for small parameter values, such as when parameterized by $b + |W^*|$ with preference lists of length 3.

Key Insights and Implications

A significant finding is the "threshold of three": while preference lists of length 2 often allow for polynomial-time solutions, increasing the length to 3 frequently triggers W[1]-hardness. Furthermore, the authors resolve a long-standing open question by Hamada et al. (2016), proving that the problem is W[1]-hard when parameterized solely by the number of blocking pairs ($b$). This indicates that simply limiting the degree of instability is insufficient to guarantee computational tractability.

Conclusion

This work provides a comprehensive guide for researchers and practitioners dealing with constrained matching problems. By identifying the exact conditions under which stable matching with lower quotas becomes tractable, it paves the way for more efficient algorithm design in complex institutional matching markets. Future work may extend these results to include preferences with ties or explore fixed-parameter approximation algorithms to further bridge the gap between theory and practice.

Summary updated

Abstract

Stable matching problems with lower quotas are fundamental in academic hiring and ensuring operability of rural hospitals. Only few tractable (polynomial-time solvable) cases of stable matching with lower quotas have been identified; most such problems are \(\mathsf {NP}\)-hard and also hard to approximate (Hamada et al. in Algorithmica 74(1):440–465, 2016). We therefore consider stable matching problems with lower quotas under a relaxed notion of tractability, namely fixed-parameter tractability. By cloning hospitals we focus on the case when all hospitals have upper quota equal to 1, which generalizes the setting of “arranged marriages” first considered by Knuth (Mariages stables et leurs relations avec d’autres problèmes combinatoires, Les Presses de l’Université de Montréal, Montreal, 1976). We investigate how a set of natural parameters, namely the maximum length of preference lists for men and women, the number of distinguished men and women, and the number of blocking pairs allowed determine the computational tractability of this problem. Our main result is a complete complexity trichotomy: for each choice of parameters we either provide a polynomial-time algorithm, or an \(\mathsf {NP}\)-hardness proof and fixed-parameter algorithm, or \(\mathsf {NP}\)-hardness proof and \(\mathsf {W}[1]\)-hardness proof. As corollary, we negatively answer a question by Hamada et al. (Algorithmica 74(1):440–465, 2016) by showing fixed-parameter intractability parameterized by optimal solution size. We also classify all cases of one-sided constraints where only women may be distinguished.
BibTeX
@inproceedings{mnich2020stable,
  author = {Matthias Mnich and Ildikó Schlotter},
  title = {{Stable Matchings with Covering Constraints: A Complete Computational Trichotomy}},
  booktitle = {Algorithmica},
  year = {2020},
  url = {https://openreview.net/forum?id=SdiwMdFWJr},
}
Figure