  Several countries successfully use centralized matching schemes for school or
higher education assignment, or for entry-level labour markets. In this paper
we explore the computational aspects of a possible similar scheme for assigning
teachers to schools. Our model is motivated by a particular characteristic of
the education system in many countries where each teacher specializes in two
subjects. We seek stable matchings, which ensure that no teacher and school
have the incentive to deviate from their assignments. Indeed we propose two
stability definitions depending on the precise format of schools' preferences.
If the schools' ranking of applicants is independent of their subjects of
specialism, we show that the problem of deciding whether a stable matching
exists is NP-complete, even if there are only three subjects, unless there are
master lists of applicants or of schools. By contrast, if the schools may order
applicants differently in each of their specialization subjects, the problem of
deciding whether a stable matching exists is NP-complete even in the presence
of subject-specific master lists plus a master list of schools. Finally, we
prove a strong inapproximability result for the problem of finding a matching
with the minimum number of blocking pairs with respect to both stability
definitions.
