  The Hospitals/Residents problem (HR) is a many-to-one matching problem whose
solution concept is stability. It is widely used in assignment systems such as
assigning medical students (residents) to hospitals. To resolve imbalance in
the number of residents assigned to hospitals, an extension called HR with
regional caps (HRRC) was introduced. In this problem, a positive integer
(called a regional cap) is associated with a subset of hospitals (called a
region), and the total number of residents assigned to hospitals in a region
must be at most its regional cap. Kamada and Kojima defined strong stability
for HRRC and demonstrated that a strongly stable matching does not necessarily
exist. Recently, Aziz et al. proved that the problem of determining if a
strongly stable matching exists is NP-complete in general. In this paper, we
refine Aziz et al.'s result by investigating the computational complexity of
the problem in terms of the length of preference lists, the size of regions,
and whether or not regions can overlap, and completely classify tractable and
intractable cases.
