Stable Matchings with Covering Constraints: A Complete Computational Trichotomy.

Area of Science:

• Computer Science
• Discrete Mathematics
• Algorithmic Game Theory

Background:

• Stable matching problems with lower quotas are computationally challenging, often NP-hard and difficult to approximate.
• Tractability has been identified in only a few specific cases, necessitating alternative approaches for broader applicability.

Purpose of the Study:

• To investigate the computational complexity of stable matching problems with lower quotas using fixed-parameter tractability.
• To analyze the impact of parameters like preference list length, distinguished individuals, and allowed blocking pairs on problem solvability.

Main Methods:

• The study employs a cloning technique for hospitals, simplifying the problem to a setting generalizing 'arranged marriages' with upper quotas of 1.
• It systematically examines various parameter combinations to determine their effect on computational tractability.

Main Results:

• A complete complexity trichotomy is established: problems are either polynomial-time solvable, NP-hard with fixed-parameter algorithms, or NP-hard with W[1]-hardness.
• Fixed-parameter intractability is proven for the parameter of optimal solution size, answering a key question in the field.

Conclusions:

• The research provides a comprehensive understanding of the computational landscape for stable matching with lower quotas under parameterized complexity.
• It offers precise classifications for one-sided constraints, advancing the theoretical foundations of matching algorithms.