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.
As shown in the summary table above, the results fall into three distinct categories:
- 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.
- 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$).
- 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