  We consider many-to-one matching problems, where one side consists of
students and the other side of schools with capacity constraints. We study how
to optimally increase the capacities of the schools so as to obtain a stable
and perfect matching (i.e., every student is matched) or a matching that is
stable and Pareto-efficient for the students. We consider two common optimality
criteria, one aiming to minimize the sum of capacity increases of all schools
(abbrv. as MinSum) and the other aiming to minimize the maximum capacity
increase of any school (abbrv. as MinMax). We obtain a complete picture in
terms of computational complexity: Except for stable and perfect matchings
using the MinMax criteria which is polynomial-time solvable, all three
remaining problems are NP-hard. We further investigate the parameterized
complexity and approximability and find that achieving stable and
Pareto-efficient matchings via minimal capacity increases is much harder than
achieving stable and perfect matchings.
