Couples Can Be Tractable: New Algorithms and Hardness Results for the Hospitals/Residents Problem with Couples

1 Introduction

1.1 Background

The STABLE MARRIAGE PROBLEM, and its many-to-one extension, the HOSPITALS / RESIDENTS PROBLEM (HR), are well-studied and central problems in Computational Social Choice, Computer Science, Game Theory and Economics, with numerous applications including in entry-level labour markets, school choice and higher education allocation [Manlove, 2013]. In the medical sphere, centralised matching schemes that assign aspiring junior doctors to hospitals operate in many countries. One of the largest and bestknown examples is the National Resident Matching Program (NRMP) in the US [NRMP website, 2024], which had just under 43,000 applicants for just over 40,000 residency positions in 2023 [NRMP data, 2024]. Canada [CARMS, 2024] and Japan [JRMP, 2024] have analogous matching schemes for junior doctor allocation.

The HR problem model represents a bipartite matching market with two-sided preferences, involving the preferences of doctors over acceptable hospitals, and those of hospitals over their applicants. Each hospital has a capacity, indicating the maximum number of doctors that it can admit. Roth [1984] argued that a key property to be satisfied by a matching M in an instance I of HR is stability, which ensures that there is no blocking pair, comprising a doctor and a hospital, both of whom have an incentive to deviate from their assignments in M and become matched to one another, undermining the integrity of M. It is known that every instance of HR admits a stable matching, which may be found in time linear in the size of I [Gale and Shapley, 1962].

In many of the above applications, there may be couples amongst the applying doctors, who wish to be allocated to hospitals that are jointly acceptable for the couple. Indeed, the NRMP matching algorithm was redesigned in 1983 specifically to allow couples to provide preferences over pairs of hospitals, with each pair representing a simultaneous assignment that is suitable for both members of the couple. We thus obtain a generalisation of HR called the HOSPITALS / RESIDENTS PROBLEM WITH COUPLES (HRC). By modifying the definition of stability, taking into account how a couple could improve relative to a matching, Roth [1984] showed that a stable matching need not exist. In HRC, the problem therefore is to find a stable matching or report that none exists. In contrast to the case for HR, Ronn [1990] showed that HRC is NP-hard.

Since then, further NP-hardness results for HRC have been established, even in very restrictive cases [Ng and Hirschberg, 1988; Ronn, 1990; Bir´o et al., 2014], suggesting that HRC is a very challenging computational problem in theory. Until now, there have been very few special cases of HRC that have been shown to admit polynomial-time algorithms. Our work in this paper extends the techniques that can be used in HRC instances by providing novel polynomial-time algorithms for variants of the problem in a surprisingly wide range of settings, and thus contributes new ways to efficiently handle specific instances in several applications.

1.2 RelatedWork

Roth [1984] considered stability in the HRC context although did not define the concept explicitly. Whilst Gusfield and Irving [1989] defined stability formally in HRC, their definition neglected to deal with the case that both members of a couple wish to be assigned to the same hospital simultaneously. There are discussions of this point in [Bir´o and Klijn, 2013] and [Manlove, 2013, Section 5.3.2]. McDermid and Manlove [2010] provided a stability definition for HRC that does deal with this possibility. A detailed study of the effects of different stability definitions for HRC was carried out by Delorme et al. [2021].

In this paper, we will adopt the stability definition of McDermid and Manlove [2010]. With respect to this definition, several algorithmic results for HRC hold. Firstly, Ronn's NPhardness result for HRC holds even in the case that each hospital has capacity 1 and there are no single doctors [Ronn, 1990] (note that all HRC stability definitions are equivalent in the unit hospital capacity case). Bir´o et al. [2014] showed that NP-hardness holds for HRC even when there are no single doctors, each couple ranks at most two pairs of hospitals, each hospital ranks at most two doctors, and all hospitals have capacity 1.

Ng and Hirschberg [1988] also proved NP-hardness for a "dual market" restriction of HRC, which we refer to as HRCDUAL, where the two sets H1 and H2, comprising the hospitals appearing in the first (respectively second) positions of the acceptable pairs of the first (respectively second) members of each couple are disjoint. This reflects the "two body" problem that often exists for couples, where, for example, one member of a couple may be applying for a job at a university, whilst the other couple member may be applying for a job in industry. Another motivating application arises in a student allocation scheme, where students apply to both a university degree programme and to an internship at a company. This can also be viewed as a specific HRC-DUAL instance, where H1 comprises the university degree programmes, and H2 the companies, and each student corresponds to a couple with one member applying to universities and the other to internships.

Manlove et al. [2017] proved that HRC is solvable in polynomial time when each single doctor and hospital has a preference list of length at most two, and each couple finds only one hospital pair acceptable. Another simple tractable case of HRC is given by Klaus and Klijn [2005] (see also [Klaus et al., 2009]), but also in a very restricted framework. They required that each couple's preference list must be weakly responsive (informally, a couple's preferences are weakly responsive if there are underlying preferences over individual hospitals for each member, such that if one member of the couple goes to a better hospital then the couple also improves), each couple must find acceptable all possible outcomes where at least one member is matched, and each hospital has capacity 1.

Given the prevalence of NP-hardness results for HRC, and the scarcity of polynomial-time algorithms, heuristics have been applied to the problem (see [Manlove, 2013, Section 5.3.3] for a survey) as well as approaches based on parameterised complexity and local search [Marx and Schlotter, 2011; Bir´o et al., 2011], integer programming [Bir´o et al., 2014; Delorme et al., 2021] and more [Manlove et al., 2017; Drummond et al., 2015].

Nguyen and Vohra [2018] studied so-called near-feasible stable matchings in HRC. They showed that if hospital capacities can be modified by at most 2, then a stable matching with respect to the new capacities always exists. However, their algorithm computes a stable fractional matching first, which is known to be PPAD-hard to compute [Cs´aji, 2022], so it is not efficient.

Another direction, to cope with the possible non-existence of a stable matching, is to consider matchings that are "as stable as possible", i.e., admit the minimum number of blocking pairs. We refer to this problem as MIN BP HRC. Bir´o et al. [Bir´o et al., 2014] showed that this problem is NP-hard and not approximable within n1-ε D , for any ε > 0, unless P=NP, where nD is the number of doctors in a given instance.

1.3 Our Contributions

In this paper, we provide new polynomial-time algorithms for HRC in the case that the couples' preference lists are subcomplete and sub-responsive. Informally, a couple's preferences are sub-complete if there are underlying preferences for the couple members, such that if both members go to a hospital that is acceptable for them individually, then the pair of hospitals is also acceptable for the couple, and if one member is willing to be unmatched, then any assignment of the other member to an acceptable hospital is acceptable for the couple. The concept of sub-responsiveness is closely related to, but a lot less restrictive than weak responsiveness as described above, even together with sub-completeness.

Our main result is a novel and surprising polynomial-time algorithm to find a near-feasible stable matching in an HRC instance if the couples' preferences are sub-responsive and sub-complete. Here, our notion of near-feasibility is based on modifying the capacities of each hospital by at most 1. This strengthens Nguyen and Vohra's [2018] result, albeit for a special case of HRC, in two ways: (i) capacities are varied by at most 1 rather than 2, and (ii) we provide a polynomialtime algorithm to produce the desired outcome. This result is established via a reduction to the STABLE FIXTURES PROBLEM (SF), a non-bipartite many-to-many generalisation of HR [Irving and Scott, 2007]. Our algorithm has other nice properties: for example, it can indeed be very beneficial for a couple to apply together, as it can happen that by applying alone, only one of them would have been matched, but by applying together, both members are matched. We illustrate this property with an example.

Next, we provide another polynomial-time algorithm for HRC in the presence of sub-responsive and sub-complete preferences that can find a stable matching, or report that none exists, if all couples are one of several possible types. One of these types corresponds to the very practical and natural restriction of HRC-DUAL in the case of sub-responsive and sub-complete preference lists, and gives a contrast to the NPhardness result of Ng and Hirschberg for general HRC-DUAL instances as mentioned earlier. Using our approach, we argue that this algorithm can potentially be extended to other types of couples, depending on the specific application.

On the structural side, we prove that a version of the classical Rural Hospitals Theorem for HR [Roth, 1984; Gale and Sotomayor, 1985; Roth, 1986] remains true even in our HRC setting with sub-responsive and sub-complete preferences, and couples belonging to one of several possible types. These are the first non-trivial classes of HRC instances that we are aware of where these structural properties hold.

We complement our positive results with several hardness results. We show that HRC is NP-hard, even with unit hospital capacities, short preference lists and other strong restrictions, including (i) sub-responsive and sub-complete couples, and (ii) dual markets and master preference lists [Irving et al., 2008]. Hence, even in these settings we may not hope to find a stable matching in polynomial time, so our algorithm to find a near-feasible stable solution becomes even more appealing.

Finally, we show that MIN BP HRC is not approximable within m1-ε , for any ε > 0, where m is the total length of the hospitals' preference lists, unless P=NP, even if each couple applies to only one pair of hospitals. This strengthens a claim made in [Manlove et al., 2017] that MIN BP HRC is not approximable within n1-ε D , for any ε > 0, where nD is the total number of doctors, unless P=NP, even if each couple applies to only one pair of hospitals. 1

Our algorithm for the case that the couples' preferences are sub-responsive and sub-complete, and the couples are one of several possible types, also helps to identify the frontier between polynomial-time solvable and NP-hard cases, as our hardness results show that if we have weaker restrictions on the couples' preferences, then it becomes NP-hard to find a stable matching. The results in this paper are summarised in Table 1.

The remainder of this paper is structured as follows. Section 2 provides definitions of key notation and terminology, and motivation for sub-responsiveness, sub-completeness and other restrictions on couples. Our polynomial-time algorithms and structural results are given in Section 3, whilst our NP-hardness and inapproximability results follow in Section 4. Finally, Section 5 concludes. All omitted proofs can be found in the full version of the paper [Cs´aji et al., 2023].

2 Preliminaries

An instance I of the HOSPITALS / RESIDENTS PROBLEM WITH COUPLES (HRC) involves a set D = {d1, d2, . . . , dnD } of single doctors, a set C = {Ci = (c2i-1, c2i) : 1 ≤ i ≤ nC} of couples, and a set H = {h1, h2, . . . , hnH } of hospitals. Let C ′ denote the members of the couples, i.e., C ′ = {c2i-1, c2i : 1 ≤ i ≤ nC}. The notation ri ∈ D ∪ C ′ denotes either a single doctor ri ∈ D or a member of a couple ri ∈ C ′ , and collectively the members of D∪C ′ are referred to as doctors.

In I there is a vector q that gives each hospital hj ∈ H a capacity qj ∈ Z+. We define a capacity vector q′ to be nearfeasible in an instance I of HRC if it holds that |q′j - qj| ≤ 1 for all hj ∈ H, that is, each capacity is changed by at most 1.

Each single doctor di ∈ D has a strict ranking ≻di over a subset A(di) ⊆ H of acceptable hospitals. Each couple Ci = (c2i-1, c2i) (1 ≤ i ≤ nC) has a set A(Ci) ⊆ ((H ∪ {∅}) × (H ∪ {∅})) \ {(∅, ∅)} of acceptable pairs of hospitals, and has a strict ranking ≻Ci over A(Ci), where

1 The proof of this result is based on a claim appearing in the supplementary material of [Manlove et al., 2017] (Theorem 8) that HRC is NP-complete even if each couple applies to only one pair of hospitals. The latter claim is erroneous and indeed HRC is solvable in polynomial time in this case as we show in Theorem 10.

∅ represents the case that a doctor is unmatched. Each entry in this list is an ordered pair of the form (hj, ∅) (∅, hk), (hj , hk), representing either one member of the couple being matched to a hospital and the other being unmatched, or both members of the couple being matched to a hospital, respectively, where hj and hk need not be distinct hospitals. We let A(c2i-1) = {hj ∈ H : (hj, ∅) ∈ A(Ci) ∨ (hj, hk) ∈ A(Ci) for some hk ∈ H}\{∅}} and A(c2i) = {hk ∈ H : (∅, hk) ∈ A(Ci) ∨ (hj, hk) ∈ A(Ci) for some hj ∈ H} \ {∅}} denote the acceptable hospitals in H for c2i-1 and c2i, respectively. Finally, each hj ∈ H has a strict ranking ≻hj over those doctors ri ∈ D ∪ C ′ such that hj ∈ A(ri).

Let M be a set of doctor-hospital pairs, i.e., a subset of (D ∪ C ′ ) × H. Given ri ∈ D ∪ C ′ , we denote {hj ∈ H : (ri, hj) ∈ M} by M(ri), and given hj ∈ H we denote {ri ∈ D ∪ C ′ : (ri, hj) ∈ M} by M(hj). We say that ri ∈ D∪C ′ is unmatched inM if M(ri) = ∅. Similarly Ci ∈ C is said to be unmatched in M if both c2i-1 and c2i are unmatched in M. Hospital hj is undersubscribed, full, or oversubscribed, if |M(hj)| < qj, |M(hj)| = qj or |M(hj)| > qj, respectively. Given Ci = (c2i-1, c2i) ∈ C, we define M(Ci) = {(hj, hk) : (c2i-1, hj) ∈ M ∧ (c2i, hk) ∈ M} ∪ {((hj, ∅) : (c2i-1, hj) ∈ M ∧ c2i is unmatched inM} ∪ {(∅, hk) : (c2i, hk) ∈ M ∧ c2i-1 is unmatched inM ∪ {(∅, ∅) : c2i-1 and c2i are unmatched inM}.

A matching is a subset M of (D ∪ C ′ ) ×H such that (i) M(di) ⊆ A(di) for each di ∈ D; (ii) M(Ci) ⊆ A(Ci) ∪ {(∅, ∅)} for each Ci ∈ C; (iii) |M(ri)| ≤ 1 for each ri ∈ D∪C ′ ; and (iv) |M(hj)| ≤ qj for each hj ∈ H. If (ri, hj) ∈ M for some ri ∈ D ∪ C ′ , as before with a slight abuse of notation we let M(ri) denote hj, and if M(Ci) = {p} for some Ci ∈ C and some p ∈ A(Ci) ∪ {(∅, ∅)} then we also let M(Ci) denote p.

We now define the concept of a blocking pair in HRC.

Definition 1 ([McDermid and Manlove, 2010]). Let I be an HRC instance and let M be a matching in I. A single doctor di ∈ D forms a blocking pair of M with a hospital hj ∈ H if:

1. (i) hj ∈ A(di), (ii) di is unmatched, or hj ≻di M(di) and (iii) hj is undersubscribed, or di ≻hj dk for some dk ∈ M(hj).

A couple Ci = (c2i-1, c2i) ∈ C forms a blocking pair of M with a hospital pair (hj , hk) ∈ (H ∪ {∅}) × (H ∪ {∅}) if (hj , hk) ∈ A(Ci), (hj , hk) ≻Ci M(Ci), and either:

1. either hj =M(c2i-1) or hk =M(c2i), and either
2. (a) hj = M(c2i-1), and either hk is undersubscribed or c2i ≻hk rs for some rs ∈M(hk)\{c2i-1}, or
3. (b) hk = M(c2i), and either hj is undersubscribed or c2i-1 ≻hj rs for some rs ∈M(hj)\{c2i}.
4. hj ̸=M(c2i-1), hk ̸=M(c2i), and either
5. (a) hj ̸= hk, and (i) hj undersubscribed or c2i-1 ≻hj rs for some rs ∈ M(hj), and (ii) hk undersubscribed or c2i ≻hk rt for some rt ∈M(hk); or
6. (b) hj = hk, and hj has at least two free posts, i.e., qj - |M(hj)| ≥ 2; or
7. (c) hj = hk, and hj has one free post, i.e., qj-|M(hj)| = 1, and cs ≻hj rt for some rt ∈ M(hj), where s ∈ {2i - 1, 2i}, or

M is stable if it admits no blocking pair.

In HRC, the problem is to find a stable matching or report that none exists. An important special case of HRC, called HRC-DUAL (i.e., a Dual Market), arises when the set H′ = ⋃ci∈C′ A(ci) of acceptable hospitals for the couple members can be partitioned into two sets H1,H2, such that for each couple Ci ∈ C, each acceptable pair (hj , hk) ∈ A(Ci) satisfies hj ∈ H1 and hk ∈ H2.

Given that an instance I of HRC may not admit a stable matching, we define MIN BP HRC to be the problem of finding a matching in I with the minimum number of blocking pairs.

Next we define some properties regarding the preference lists of couples.

Definition 2. Let Ci = (c2i-1, c2i) be a couple with joint preference list ≻Ci .

1. We say that ≻Ci is sub-responsive if there are preference orders ≻c2i-1 ,≻c2i over A(c2i-1) ∪ {∅} and A(c2i) ∪ {∅} for the individual members of the couple such that, for any three hospitals hj , hk, hq in H ∪ {∅},
2. (i) if ((hj, hk) ∈ A(Ci) and (hj, hq) ∈ A(Ci)) then ((hj, hk) ≻Ci (hj, hq) if and only if hk ≻c2i hq), and
3. (ii) if ((hj, hk) ∈ A(Ci) and (hq, hk) ∈ A(Ci)) then ((hj, hk)≻Ci (hq, hk) if and only if hj ≻c2i-1 hq).

That is, there are underlying preferences for each member of the couple, such that if we send one of them to a better hospital, then the couple also improves, assuming that the new pair is acceptable.

1. We say that ≻Ci is sub-complete if A(Ci) = (A′ (c2i-1) × A′ (c2i)) \ {(∅, ∅)}, where, for j ∈ {0, 1}, either A′ (c2i-j ) = A(c2i-j ) or A′ (c2i-j ) = A(c2i-j )∪ {∅}. That is, if both members go to an acceptable hospital for them, then the pair of hospitals is also acceptable for the couple, and if one member is willing to be unmatched, then any assignment of the other member to an acceptable hospital is acceptable for the couple.

We say that Ci is sub-responsive or sub-complete if ≻Ci is sub-responsive or sub-complete, respectively.

As we show in Theorem 14, HRC remains NP-hard even with sub-responsive and sub-complete preference lists. However, in Theorem 10, we provide a novel reduction to SF that allows us to deal with many different kinds of couples via a polynomial-time algorithm. To this end, we define SF, and then some special types of couples.

In an instance of SF, we are given a graph G = (V,E), where each vertex v ∈ V has a strict preference list ≻v over the edges incident to v. We are also given a capacity b(v) for each v ∈ V . A b-matching is a set M ⊆ E such that |M(v)| ≤ b(v) for each v ∈ V , where M(v) is the set of edges in M that are incident to v. M is stable if M admits no blocking pair, which is an edge e = {u, v} ∈ E such that, for each w ∈ e, either |M(w)| < b(w) or e ≺w e′ for some e′ ∈M(w).

Definition 3. We say a sub-responsive and sub-complete couple Ci = (c2i-1, c2i) is

• separable, if A(Ci) = (A(c2i-1) ∪ {∅}) × (A(c2i) ∪ {∅}) \ {(∅, ∅)} (that is, it is allowed to match only one member of the couple in a feasible matching),
• half-separable if A(Ci) = A(c2i-1)×(A(c2i)∪{∅}) or (A(c2i-1)∪{∅})×A(c2i) (that is, it is allowed to leave at most one member of the couple unmatched, but this can only ever be one designated member),
• connected, if A(Ci) = A(c2i-1) ×A(c2i) (that is, both couple members must be matched),
• of type-a, if A(c2i-1)∩A(c2i) = ∅ (that is the twomembers apply to distinct hospitals),
• of type-b, if it is connected, A(c2i-1) ∩ A(c2i) = {h} and if c2i-1 ≻h c2i, then A(c2i) = {h}, otherwise A(c2i-1) = {h} (that is, the worse member for h only applies to h)
• of type-c, if it is connected, A(c2i-1) ∩ A(c2i) = {h} and for any h ̸= h′ ∈ A(c2i-1), h′ ≻c2i-1 h and for any h ̸= h′′ ∈ A(c2i), h′′ ≻c2i h, (that is, h is the worst hospital for both members of the couple).

To avoid collision, we consider a couple Ci that is both of type-b and -c, simply as a type-b couple.

We will show that HRC is solvable in polynomial time for couples of type-a, -b or -c. Moreover for Dual Markets, every couple is necessarily of type-a. However, every couple being of type-a is more general than HRC-DUAL, as it only means that for each couple Ci, the acceptable hospitals for each member of Ci are two disjoint sets. To illustrate this with a simple example, suppose there are three hospitals h1, h2, h3 and three couples C1,C2,C3. C1 applies only to (h1, h2), C2 applies only to (h2, h3), and C3 applies only to (h3, h1). Then, every couple is type-a, but the market is not dual.

Motivation. We finally provide some motivation for the couple types given in Definitions 2 and 3. Firstly, in the Dual Market example given in Section 1, where each "couple" is a student who applies to both a university and a company, the underlying mathematical problem is HRC-DUAL. It is natural to assume that preferences are sub-responsive and subcomplete in this case, and all couples are thus of type-a as observed above.

Types-b and -c may seem a little more artificial. On the one hand, they will demonstrate the flexibility of our technique such that it can handle couples even if they apply to the same hospital. On the other hand, there may be applications related to HRC where these types of (sub-responsive and subcomplete) structures arise, especially in scenarios where it is better for a couple (or an agent) to obtain a joint allocation where the two assigned positions are more diverse. Imagine for example that two members of a couple apply to part-time positions, which also have associated shifts (indicating which days they have to attend). Then, a couple may prefer their shifts to be on different days, to minimise the amount of daycare needed for their children. For example, if one of them applies to shifts on days 1, 2 and 3, and the other on days 3, 4 and 5, then it is natural to assume that they express a subresponsive and sub-complete preference list, such that (3,3) is ranked last, hence they give a type-c couple. Our preliminary results show that we can handle even more types of couples using our techniques, including those that may arise in other applications, but in order not to make the proofs extremely technical, we only consider the couple types defined in Definitions 2 and 3 in this paper.

We also note the important special case of HRC in which each couple applies only to one pair of hospitals. Then as per the proof of Corollary 11, each couple is type-a or -b. On the other hand, HRC is NP-hard even if each couple finds acceptable only two hospital pairs [Bir´o et al., 2014]. This helps to push forward our understanding of the frontier between polynomial-time solvability and NP-hardness for restrictions of HRC. Indeed, couple structures that do not make the problem NP-hard may need to be very specific, as Theorem 14 shows that HRC remains NP-hard even with sub-responsive and sub-complete couples, such that each member of a couple applies to only two hospitals.

As a more theoretical application, types-a, -b and -c also arise when we model a new multigraph extension of SF where loop edges are allowed. Due to space constraints, this problem is not discussed in the current version of this paper. Finally, we note that even in cases where there may be different types of couples (beyond those defined in Definitions 2 and 3), it may speed up heuristics and IP techniques to first compute (in polynomial time) a stable solution restricted to the single doctors and the couples of types-a, -b and -c.

3 Polynomial Time Algorithms

In this section we describe our main positive results. We start by describing our most practical polynomial-time algorithm to find a near-feasible stable matching in any HRC instance I, where the participating couples have sub-responsive and sub-complete preference lists.

Theorem 4. Given an HRC instance where each couple's preferences are sub-responsive and sub-complete, there is always a near-feasible capacity vector q′ where |q′ - q|∞ ≤ 1, such that there is a stable matching with respect to the modified capacities. Furthermore, these modified capacities and the stable matching can be found in O(m) time, where m denotes the total length of the preference lists of the hospitals.

Proof. We prove our statement by providing a polynomialtime reduction of the problem to SF. Then, we proceed by finding a fractional stable solution and round it off in a specific way to obtain a near-feasible stable matching.

Let I = (D,C,H, q,≻) be an instance of HRC where the couples' preferences are sub-responsive and sub-complete. We transform I to a SF instance I ′ , and start by describing the vertices and the capacities in I ′ .

• For each single doctor di ∈ D, we just create a vertex di with capacity 1.
• For each hospital hj with capacity qj, we just create a vertex hj with capacity qj .
• For each couple Ci = (c2i-1, c2i) we create two vertices c2i-1 and c2i with capacity 1; and if Ci is connected, we create connector vertices a2i-1, a2i, b2i-1, b2i with capacity 1.

We proceed by describing the edges of I ′ .

• For each single doctor di and an acceptable hospital hj, we add edge (di, hj).
• For each couple Ci = (c2i-1, c2i) with acceptable hospitals A(c2i-1), A(c2i):
• we add the edges (c2i-1, hj), ∀hj ∈ A(c2i-1), and edges (c2i, hj), ∀hj ∈ A(c2i),
• if Ci is half-separable, then we add (c2i-1, c2i),
• if Ci is connected, we add the edges (c2i-1, a2i-1), (a2i-1, b2i-1), (b2i-1, c2i), (c2i, a2i), (a2i, b2i), (b2i, c2i-1).

Finally, we give the preference lists of the created vertices over their neighbours.

• For each single doctor di, we just keep his preference list over the hospitals.
• For each hospital hj, it just keeps its preference list over the doctors.
• For each member ck of a half-separable couple, if ck is the one that can be assigned alone, then he ranks the hospitals in A(ck) according to ≻ck , followed by his partner ck′ last. If ck is the member who cannot be assigned alone, then ck ranks ck′ first, and then the hospitals in A(ck).
• Let ck be a member of a non-half-separable couple. The preferences of ck in I ′ are then created such that he/she ranks ak first (if it exists), followed by the hospitals in A(ck) according to ≻ck , and bk-1 or bk+1 last (depending on the parity of k, again, if it exists).
• For the additional ak, bk vertices we have that b2i-1 ≻a2i-1 c2i-1, c2i ≻b2i-1 a2i-1, b2i ≻a2i c2i and c2i-1 ≻b2i a2i.

With a modification of the algorithm of Tan [1991], described by Fleiner [2010], we can find a stable half-integral matchingMf in I ′ in time O(|E|) = O(m). That is, for each edge (u, v) ∈ E, Mf (u, v) ∈ {0, 12 , 1}, for each vertex u ∈ V , ∑(u,v)∈E Mf(u, v) ≤ qv (qv is the created capacity for v), and for each edge (u, v) with Mf (u, v) < 1, it holds that either u or v is saturated in Mf (i.e., ∑(w,x)∈E Mf (w, x) = 1 for some w ∈ {u, v}) with partners that are at least as good as (u, v). Then, we say that (u, v) is dominated at that vertex. We start with an important observation.

Observation 5. In Mf , each vertex is incident to either 0 or two incident fractional edges.

Proof. First note that each fractional edgemust be dominated at one endpoint, as Mf is stable. Orient each of the edges towards a vertex that dominates it. Then, there can be at most one incoming arcs into each vertex, because if there would be two, then the better one of them would not be dominated there, contradiction. Also, if there is one incoming arc to a vertex, then there is an outgoing arc too, as for the vertex to be saturated, there must be another fractional adjacent edge.

We create a set of pairs M in I as follows. For each doctor ri ∈ D ∪ C ′ , let Si = {hj ∈ A(ri) : Mf(ri, hj) > 0}. If Si ̸= ∅, add to M the edge (ri, hj) such that hj is the mostpreferred (according to ≻ri ) member of Si. (If Si = ∅, no edge incident to ri is added toM.) For each hospital hj ∈ H, we modify hj's capacity in I ′ as follows: if hj was saturated in Mf then we set q′j = |M(hj)|, otherwise we set q′j = qj.

Claim 6. The obtained matchingM is a near-feasible stable matching in I with respect to the new capacities.

Proof. Feasibility. First of all we have to show that M defines a feasible matching in I. Clearly, every doctor ri is assigned to at most one hospital inM. If ri is a single doctor, then it is clear that M(ri) is acceptable to him.

If ri is a member of a connected couple, say (by symmetry) c2i-1, who is matched in M, then we first show that his partner c2i is also matched in M. Suppose for the contrary that c2i is not matched inM. Then, c2i is not matched to any hospital vertex hj with positive weight in Mf . As the edge (b2i-1, c2i) does not block Mf , we obtain that c2i must be saturated in Mf . Hence Mf(c2i, a2i) + Mf(b2i-1, c2i) = 1. As each of {a2i-1, a2i, b2i-1, b2i, c2i-1, c2i} are a strict first choice of some other agent, all of them must be saturated in Mf . Therefore, if x = Mf(c2i, a2i), then 1 - x = Mf(b2i-1, c2i) = Mf(a2i, b2i), hence x = Mf(b2i, c2i-1) = Mf(a2i-1, b2i-1) and 1 - x = Mf(c2i-1, a2i-1). But this implies that Mf(c2i-1, a2i-1) + Mf(b2i, c2i-1) = 1, which contradicts the fact that c2i-1 is matched to a hospital in M. Hence, for each couple Ci, neither or both of them are matched.

If ck is a member of a half-separable couple who cannot be assigned alone, then we show that ck is assigned only if his partner ck′ is too. Indeed, if ck′ is not matched to a hospital, but ck is, then ck′ is not matched with weight 1 inMf , and as the edge (ck, ck′) is the best for ck, we get that it blocks Mf , contradiction.

Also, because every couple's preferences are subcomplete, we obtain that no matter which hospitals in A(c2i-1) and A(c2i) are assigned c2i-1 and c2i in M, it must be the case that (M(c2i-1),M(c2i)) ∈ A(Ci). Hence each couple finds the created allocation feasible too.

Finally, we show that no hospital is oversubscribed in M. Obviously, only the hospitals whose capacity we do not change to |M(hj)| can become oversubscribed. But these hospitals were undersubscribed, and it follows by Observation 5 that the number of doctors it obtains in M is at most |Mf (hj )| + 1 ≤ qj .

The new capacities are near-feasible. Next we show that the new capacities are near-feasible, that is each capacity is changed by at most 1. Suppose we changed a hospital's capacity to |M(hj)|. Then, hj was saturated inMf and it had at most two incident fractional edges and all of these edges were to vertices corresponding to doctors. Hence, after the rounding, qj - 1 = |Mf (hj)| - 1 ≤ |M(hj)| ≤ |Mf (hj)| + 1 = qj + 1.

Stability. Finally we show that the created matching M is stable with respect to the new capacities.

Suppose that a single doctor di blocks with a hospital hj. Then, by the creation of M, we know that Mf (di, hj) = 0. But, the edge (di, hj) did not block Mf , so hj was filled with better, possibly fractional partners in Mf , each of them being vertices corresponding to doctors. By the definition of the new capacities, hj remains saturated, and any doctor at hj in M must have been at hj with positive weight in Mf . Therefore, hj is filled with better doctors than di, a contradiction.

Suppose that a couple Ci ∈ C blocks M in I with a pair of hospitals (hj, hk) ∈ A(Ci). The following argument holds regardless of whether hj = hk or not. By the assumption that the couple's preferences are sub-responsive, it follows that either Ci is unmatched in M (in which case one of the members cannot be matched to vertices better than his hospital partners with weight 1 in Mf ), or one of its members c2i-1 or c2i is at a worse hospital according to his ranking. Suppose by symmetry that this member is c2i. By the construction of M, it follows that Mf(c2i, hk) = 0 must hold. But the edge (c2i, hk) did not block Mf in I ′ , so hk was saturated in Mf with better partners than c2i, all of them being doctors. Hence, we obtain again by our construction that hk is full in M with better doctors than c2i, contradiction.

Suppose a couple Ci blocks with one hospital and an application (hi, ∅) or (∅, hj). In this case, Ci must be separable or half-separable. Suppose by symmetry that c2i is the one who gets matched to a hospital in the blocking coalition. Then, if Ci is half-separable, then c2i must be the member who can be assigned alone, so he ranks c2i-1 last. Hence, in any case, c2i cannot be matched to better partners in Mf than hj, and Mf(c2i, hj) = 0. But (c2i, hj) does not block Mf , so hj was saturated with better doctors in Mf , so it still is in M, contradiction.

Therefore, we obtain that the matching M is stable too, proving the theorem.

Remark 7. We first remark that this algorithm extends in a straightforward way to the case where ties are allowed in the preference lists, as a stable half-integral matching can be found even if ties are allowed.

Remark 8. By the result of Nguyen and Vohra [2018], we know that there is always a near-feasible stable matching in any HRC instance, if we can change the capacities by 2 instead of 1. However, there is no known polynomial-time algorithm to find such capacities and a stable matching.

In the HRC problem, especially with sub-responsive and sub-complete preferences, it might be unclear as to why it is beneficial for a couple to apply together to pairs of hospitals. Indeed, any stable matching would be stable even if they would have applied separately, however, by applying together it is possible that neither of them gets matched in the end, whereas one of them could have been matched if they had applied separately. However, a very nice feature of our algorithm as given in the proof of Theorem 4 is that now it may be very beneficial for a couple to apply together, as demonstrated below.

Example 9. Let h be a hospital with capacity 2. Suppose there is one single doctor d and a couple (c1, c2). Every doctor applies only to h, which has preference list c1 ≻h d ≻h c2. Then, if the two members of the couple would apply as separate doctors, the output matching would be to assign c1 and d to h, and leave c2 unmatched. However, if c1 and c2 apply together as a connected couple, then in the fractional stable matching Mf , d is assigned to h with weight 1, while c1 and c2 are both assigned to h with weight 0.5. Hence, in the output of the algorithm, the capacity of h is increased by 1, and both c1 and c2 are accepted.

We continue to our other main theorem of this section.

Theorem 10. HRC is solvable in O(m) time, whenever each couple is sub-responsive, sub-complete and is of type-a, -b or -c, where m denotes the total length of the preference lists of the hospitals.

The proof of Theorem 10 is complex and technical; here we describe the main underlying ideas and techniques only. As in Theorem 4, we reduce the problem to SF, which can be solved in O(m) time [Irving and Scott, 2007]. For each couple type, we carefully design different types of gadgets, building on the couple gadgets used in Theorem 4, that enable us to preserve the property that the HRC instance has a stable matching if and only if the SF instance does. We also split the vertices in the SF instance corresponding to the hospitals, such that we have a vertex of capacity 1 that corresponds to the worst doctor at h, and delete some edges incident to this new vertex (since, e.g., if a couple Ci has only one application (h, h), then the better member of Ci for h cannot be the worst doctor at h) which is a crucial idea to handle couples that apply to the same hospital.

We next make a simple observation about separable couples. If every couple were separable, then by treating each member as just a single doctor and running the doctororiented Gale-Shapley algorithm [Gusfield and Irving, 1989] we could always obtain a stable matching. This demonstrates that separable couples are easier to handle and indeed it is one of the main reasons that we consider mostly connected couple types (type-b and type-c). We could extend our technique to other separable and half-separable couple types, but it would make both the statement and the proof of Theorem 10 significantly more technical.

Theorem 10 has some interesting corollaries.

Corollary 11. HRC is solvable in polynomial time if each couple only applies to one pair of hospitals.

Corollary 12. HRC-DUAL is solvable in polynomial time if each couple is sub-responsive and sub-complete. Furthermore, there always exists a stable matching.

We can also show that a variant of the Rural Hospital theorem also extends to this framework.

Corollary 13. Given an HRC instance where each couple is of type-a, -b or -c, in every stable matching, the same set of single doctors are matched and every hospital has the number of doctors. Furthermore, if a hospital is undersubscribed in one stable matching, then it is assigned the same set of doctors in all stable matchings.

4 Hardness Results

In this section we present hardness results for three variants of HRC. We firstly consider sub-responsive and subcomplete preferences. It might be tempting to believe that sub-responsive and sub-complete preferences are sufficient to guarantee the polynomial-time solvability of HRC. However, it turns out that these assumptions are unfortunately not enough, as the following result demonstrates.

Theorem 14. HRC is NP-hard even if each couple has subresponsive and sub-complete preferences. This holds even with unit hospital capacities, and even if each preference list is of length at most 4. This also holds if either (i) the couples are half-separable, or (ii) every couple is separable or of type-a, in which (in both cases) each preference list is of length at most 8.

We next consider dual markets, and we show that the hardness holds in restricted cases of HRC-DUAL too.

Theorem 15. HRC-DUAL is NP-hard, even if all preference lists have length 3, all hospitals have capacity 1, and the preference list of each single doctor, couple and hospital is derived from a strictly ordered master list of hospitals, pairs of hospitals and doctors, respectively.

We finally state our inapproximability result for MIN BP HRC.

Theorem 16. MIN BP HRC is not approximable within m1-ε , for any ε > 0, where m is the total length of the hospitals' preference lists, unless P=NP. The result holds even if there are no single doctors, every couple finds acceptable only one pair of hospitals, and each hospital has capacity 1.

5 Conclusions

In this paper, we have presented a range of novel polynomialtime solvability and NP-hardness results for variants of HRC. An important future direction is to continue to expand our knowledge of the frontier between tractable and intractable variants of HRC. A key message from this paper, however, is that HRC can be tractable in a range of different scenarios, and perhaps much more so than might have been predicted previously, given the inherent intractability of the problem in general and in so many restricted settings.

Ethical Statement

There are no ethical issues.

Acknowledgements

Gergely Cs´aji was supported by the Hungarian Academy of Sciences, Momentum grant number LP2021-2/2021, by the Hungarian Scientific Research Fund, OTKA, grant number K143858 and by the Ministry of Culture and Innovation of Hungary from the National Research, Development and Innovation fund, financed under the KDP-2023 funding scheme (grant number C2258525). David Manlove was supported by the Engineering and Physical Sciences Research Council, grant numbers EP/X013618/1 and EP/P028306/1. Iain McBride was supported by a Scottish Informatics and Computer Science Alliance Prize Studentship. James Trimble was supported by the Engineering and Physical Sciences Research Council, Doctoral Training Partnership number EP/N509668/1. For the purpose of open access, the authors have applied a Creative Commons Attribution (CC BY) licence to any Author Accepted Manuscript version arising from this submission.