{'fraction_non_alphanumeric': 0.039519906323185014, 'fraction_numerical': 0.012680266239368914, 'mean_word_length': 4.055300257029364, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Finding all Stable Matchings with Assignment Constraints

In this paper we consider stable matchings that are subject to assignment constraints. These are matchings that require certain assigned pairs to be included, insist that some other assigned pairs are not, and, importantly, are stable. Our main contribution is an algorithm that determines when assignment constraints are compatible with stability. Whenever a stable matching consistent with the assignment constraints exists, our algorithm will output all of them (in polynomial time per solution). This provides market designers with (i) a tool to test the feasibility of stable matchings with assignment constraints, and (ii) a separate tool to implement them.


Introduction
In a two-sided market with workers on one side and firms on the other, a stable matching is an assignment of workers and firms from which joint deviations do not pay. The specific environment we consider in this paper is the many-to-one variant of two-sided markets, and our focus is on stable matchings with assignment constraints. These are matchings that require some worker-firm pairs to be included, insist that some other worker-firm pairs are not, and, importantly, are stable.
Consider the following example of a labour market for junior doctors that operates (like many entry-level labour markets) via centralised matching protocols. There is a market designer who is eager for doctor A, whose speciality is cardiology, to be matched with one of the four rural hospitals that wish to fill their open position with a cardiologist. The market designer is also keen for doctor B, whose speciality is paediatrics, not to be employed at the downtown hospital as the paediatrics department there is already well-staffed. Suppose further that these two requirements are "all that really matter" to the market designer in that how the remaining market participants are matched is so unimportant as to be immaterial. Naturally the market designer would like to know: does there exist a labour market equilibrium (a stable matching) that adheres to these criteria?
Questions like the above can be addressed by defining assignment constraints.
Definition. Consider a many-to-one two-sided market with workers, W , on one side and firms, F , on the other. A list of assignment constraints is defined by a subset of workersŴ ⊆ W and a subset of firmsF ⊆ F such that (i) for each worker w ∈Ŵ , there is either a subset of firms, F in (w), one of which must be w's employer, or there is a subset of firms, F out (w), at which w must not be employed, or there are both.
(ii) for each firm f ∈F , there is a subset of workers, W in (f), such that the positions at f must be filled by workers from the subset, or there is a subset of workers W out (f), each of whom must not be employed at f, or there are both.
The main contribution of this paper is an algorithm that addresses the following generalisation of the market designer's question above.
Constrained Stable Matchings: Given a many-to-one two-sided market and a list of assignment constraints, is there is a stable matching that satisfies the assignment constraints? If the answer is yes, generate all such stable matchings.
Clearly the outcomes that a market designer desires may not be feasible. 1 The reason is immediate: it is the preferences of the individual market participants, and not those of the designer, that determine which outcomes are stable. And implementing an outcome that is not stable -no matter how desirable to the designer -seems ill-advised as it will surely unravel. Given this, it would be useful for the market designer to know if and when assignment constraints are consistent with stability. Our algorithm allows the market designer to do precisely this. Moreover, our algorithm outputs any and all stable matchings compatible with the constraints. (In the absence of any constraints, our algorithm will output every stable matching for the two-sided market in question.) In a big picture sense, the study of stable matchings with assignment constraints allows one to address questions of the form: "is there a stable matching in which...?" We will show that such questions are in fact equivalent to the following, seemingly far simpler, problem.
Reduced Constrained Stable Matchings: Given two disjoint collections of worker-firm pairs C in and C out , is there is a stable matching that includes all worker-firm pairs in C in and does not include any worker-firm pair in C out ? If the answer is yes, generate all such stable matchings.
That is, we will show that questions concerning stable matchings with assignment constraints reduce to a study of what combinations of pairs are consistent with stability. There is a well-known analog concerning what combinations of individual market participants are consistent with stability. The celebrated result known as the rural hospitals theorem confirms that if a market participant is not matched in some stable matching then they are never matched in any. 2 By virtue of the rural hospitals theorem, knowledge of a single stable matching allows the identification of which workers will be employed and which positions will be filled in every equilibrium, thereby answering the analog of Reduced Constrained Stable Matchings for individuals. 3 The rural hospitals theorem is not only of theoretical interest but has an important practical consequence for market design. The result highlights that a market designer who insists on stability is powerless in influencing "which collections of individuals are in" and "which collections of individuals are out". That is, the most that a market designer can hope to achieve by varying the matching protocol is to impact who those that "are in" will be paired with. As stated earlier, we show that stable matchings with constraints is equivalent to considering "which collections of worker-firm pairs are in" and "which collections worker-firm pairs are out". This seems worthy of study as not only are pairs the underpinnings of stability, but this is where a market designer actually holds some sway. For this reason we hope that our results will be of interest to practitioners of market design and not purely of theoretical interest.
We will not provide a detailed overview of how our algorithm operates here.
2 The observation that the same market participants appear in every stable matching was made first by McVitie and Wilson (1970) for the original one-to-one matching environment. This result was extended to the richer many-to-one matching environment in Roth (1984) and Gale and Sotomayor (1985a,b) where it was also noted that those on the side of the "one" are matched with the same number of individuals in every stable matching. Roth (1984) was a study of the National Resident Matching Program (the NRMP -the system in the United States that matches junior doctors to hospitals), and as a consequence this finding became known as "the rural hospitals theorem" due to the fact that the underserved hospitals (that are always underserved) were often to be found in rural locations. The result was further extended in Roth (1986) where it was shown that any hospital with unfilled positions in some stable matching is in fact assigned the exact same residents in every stable matching.
3 To see how closely related the two issues are consider the following. Had we referred to Reduced Constrained Stable Matchings by the equally appropriate name of Stable Match Checking for Pairs, then the deferred acceptance algorithm of Gale and Shapley (1962) provides an answer to Stable Match Checking for Individuals, i.e., our rebranded question with the word "Pairs" replaced by the word "Individuals".
(A complete guide is given in Subsection 4.2 using the paper's working example Example 1.) Rather, we will simply mention that the key tool in our approach is the iterated deletion of unattractive alternatives (IDUA) and briefly sketch why it is useful. 4 IDUA is a procedure that reduces a matching problem by repeatedly deleting worker-firm pairs that cannot be part of any stable matching. Once the procedure stops -and it must -what remains is the normal form: a (sub)matching market that contains all the essential information of the original market in that the set of stable matchings remains unchanged (see Lemma 1). Not only is the normal form of a many-to-one two-sided market always balanced -one with an equal number of workers and positions -but a balanced market wherein the stable outcomes have every worker employed and every vacancy filled (see Lemma 3). 5 To see how IDUA facilitates investigating the feasibility of various constraints, suppose that worker-firm pair (w, f) is not part of the normal form. Then by definition there is no stable matching in which w is employed at f. But suppose the pair (w, f) is part of the normal form, and the market designer would like to know if there is an equilibrium in which w is not employed at f. Such a requirement has consequences. Not only can (w, f) not be included in a desired stable matching, but since w will always be employed and the position at f will always be filled, it must also be the case that (w, f) is not a blocking pair against any candidate outcome. Running IDUA on an appropriate modification of the normal form (wherein the pair (w, f) is assigned special status) captures the knock on effects of this requirement and is the crucial ingredient of our algorithm.
In theory Constrained Stable Matchings can be answered by brute force. First one uses an algorithm that finds every stable matching (e.g., Martínez et al. (2004);Bonifacio et al. (2022)), and then one checks each stable matching against the constraints. 6 The drawback to such an approach is that the number of stable 4 IDUA was introduced first in Balinski and Ratier (1997) and used by us in a previous paper, Gutin et al. (2021), to classify unique stable matchings. 5 As such, restricting attention to perfect stable matchings (those in which all workers are employed and all positions are filled), typically viewed as a simplifying assumption, is in fact without loss of generality.
6 Both Irving and Leather (1986) and Gusfield (1987) present algorithms that output every stable matching (albeit both consider the less applicable one-to-one matching markets with complete matchings for a given instance can be exponential (Knuth, 1996), and so, despite the fact that each solution can be checked in polynomial time (Gusfield, 1987), checking all of them may not be feasible in practice. Our algorithm that addresses Constrained Stable Matchings also spends a polynomial amount of time per solution, and so we believe our algorithm will be of most value when the set of constraints is large in which case there are likely to be few solutions.
We conclude the introduction by relating our work to that of others. The literature to which our paper is closest falls under the umbrella term of "matchings with constraints" (Kamada and Kojima (2017) is a survey). One of the most important implications of constraints is that they may prove a barrier to the existence of stable outcomes. As such, there is a growing literature that proposes matching mechanisms for such environments. Our paper can be viewed as a first check on whether it is indeed the case that a particular matching market with constraints requires that stability be relaxed.
To the best of our knowledge, the first paper to consider external constraints is the Roth (1984) study of the NRMP mentioned in Footnote 2. Amongst other things, Roth considered the consequences of two residents who are a couple in their private life and, for example, may desire to work at the same hospital above all else. Roth showed that satisfying constraints of this type may be incompatible with stability. 7 Kojima (2015) presents an algorithm, adapted from that of Echenique and Yenmez (2007), that outputs all stable matchings with couples. Ehlers et al. (2014) consider school choice problems where students are of different types and the market designer would like to maintain diversity requirements across schools. In practice, diversity constraints are often enforced by setting hard upper bounds and hard lower bounds for each student type at the local (school) level. Motivated by the Japanese medical residency market upon which the Japanese government imposed "regional caps" for each of Japan's 47 prefectures, Kamada and Kojima (2015) introduce "matchings with distributional constraints". These constraints are of a more global nature, taking the form of restrictions on the numbers of doctors matched to certain subsets of hospitals. For both of these constrained environments stability can be too strong a requirement and so various weaker solution concepts are proposed.
While we view our algorithm's applicability to questions of interest as this paper's main contribution, we also believe that our algorithm has one marked advantage over many others in the literature. That advantage is its simplicity. Many of those papers listed above use machinery that is not only quite involved but is also difficult to ascribe any economic meaning to. 8 This stands in stark contrast to our methods that are simple, based on the intuitive IDUA procedure, and even have a nice graphical interpretation (see for example Figure 6). In essence we examine directly the consequences on market outcomes of imposing assignment constraints and carefully document the knock on effects.
The remainder of the paper is organised as follows. Section 2 introduces many-toone matching problems, converts these problems to an equivalent formulation using directed graphs (all our results are obtained using this formulation), and restates our question of interest. Section 3 presents the IDUA algorithm that reduces every matching problem to its normal form. For the reader's convenience Section 4 is split into two parts. In Subsection 4.1 we formally state our algorithm and prove its correctness. In Subsection 4.2 we demonstrate how the algorithm works by laboriously working through a particular set of queries that a market designer might have about labour market equilibria in the paper's working example Example 1.

Constrained matching problems and their associated digraphs
In Section 2.1 we define matching problems with assignment constraints. In Section 2.2 we show how the study of matching problems with assignment constraints can be reduced to a seemingly simpler question concerning specific pairs. In Section 2.3 we show how to reformulate matching problems with assignment constraints using directed graphs, by extending this representation of matching problems, originally due to Maffray (1992), to include assignment constraints.

Matching problems with assignment constraints
The participants in a many-to-one two-sided matching market consist of two disjoint sets of workers and firms. 9 Let W denote the set of m workers and let F denote the set n of firms. Each firm f ∈ F has a quota, q(f), that represents the maximum number of workers for which f has positions. Each worker w ∈ W can hold at most one position.
Participants have preferences over those on the other side of the market. That is, each worker w ∈ W has a strict preference ordering over some nonempty list of firms in F , and each firm f ∈ F has a strict preference ordering over some nonempty list of workers in W . If f is not on the preference list of worker w, we interpret this as w would prefer to be unmatched over being matched with f. An analogous statement holds for the preference lists of firms. Finally, we make the simplifying assumption that firm f is on the preference list of worker w if and only if worker w is on the preference list of firm f. Definition 1. An instance, P , of the many-to-one matching problem is a set of m workers, W , a set of n firms, F , and a collection of m + n preference lists, one for each worker and one for each firm.
A matching, µ, in a many-to-one matching problem, P , is a collection of pairs from W × F , such that every worker w ∈ W appears in at most one pair, and every firm f appears in at most q(f) pairs. If the worker-firm pair (w, f) is contained in matching µ, we will say that (w, f) is a matched pair in µ.
The following is the key definition of Gale and Shapley (1962), modified for the many-to-one two-sided environment of this paper.
Definition 2. We say that worker w and firm f form a blocking pair with respect to matching µ in P , if both prefer each other over their current assignment in µ. That is, (w, f) is not a matched pair in µ and (i) w is not in a matched pair in µ and f is not in a matched pair in µ, or (ii) w is not in a matched pair in µ, f is in a matched pair with w and yet f prefers w to w , or (iii) f is in strictly less than q(f) matched pairs in µ, and w is in a matched pair with f and yet w prefers f to f , or (iv) f is in q(f) matched pairs, w is in a matched pair with f and there is a worker w in a matched pair with f and both w prefers f to f and f prefers w to w .
The solution concept that Gale and Shapley (1962) proposed is termed stability and is defined by the absence of a blocking pair.
Definition 3. A matching µ in P with no blocking pairs is a stable matching.
As mentioned in the introduction, we envisage a hypothetical market designer who is faced with a particular matching problem. Clearly the market designer's preferences over matchings may differ from those of the market participants. And if so, the market designer faces a trade off between stability and feasibility. Trade offs can be explored by posing a catalogue of queries about whether various requirements are consistent with stability.
Questions like that of the market designer in the introduction can described by assignment constraints as follows. (While we already provided Definition 4 below in the introduction, we repeat it here to make this section self-contained. We do likewise for both Constrained Stable Matchings and Reduced Constrained Stable Matchings.) Definition 4. For a given many-to-one matching problem (see Definition 1) a list of assignment constraints is defined by a subset of workersŴ ⊆ W and a subset of firmsF ⊆ F such that (i) for each worker w ∈Ŵ , there is either a subset of firms, F in (w), one of which must be w's employer, or there is a subset of firms, F out (w), at which w must not be employed, or there is both.
(ii) for each firm f ∈F , there is a subset of workers, W in (f), such that the positions at f must be filled by workers from the subset, or there is a subset of workers W out (f), each of whom must not be employed at f, or there is both.
For a given list of assignment constraints, the market designer would like to know whether there is a stable matching consistent with the list. If yes, the market designer would then like to know all such stable matchings. The market designer is thus faced with the following problem that is the main motivation of our paper.
Constrained Stable Matchings: Given a many-to-one stable matching problem and a list of assignment constraints, is there is a stable matching that satisfies the assignment constraints? If the answer is yes, generate all such stable matchings.
We now provide an example of a many-to-one matching problem with assignment constraints. This will be our working example throughout.
Example 1. Consider a many-to-one two-sided matching problem with six workers, W = {w 1 , w 2 , w 3 , w 4 , w 5 , w 6 }, and four firms, F = {f 1 , f 2 , f 3 , f 4 }. The firms' quotas are given by q(f 1 ) = q(f 2 ) = q(f 3 ) = 1 and q(f 4 ) = 2. The preference lists for each worker and each firm are presented below, with the market participants on the other side of the market listed in order of decreasing preference. 10 Now return to the hypothetical market designer. Suppose that, for whatever reason, the market designer wants to know if there is a stable matching in which either worker w 1 or worker w 6 is employed at firm f 2 , worker w 4 is not employed at firm f 1 , and worker w 6 is not employed at firm f 4 ? In the language of Definition 4, the market designer would like an answer to the following question: Question 1. Given the stable matching problem defined above, is there a stable matching consistent with the assignment constraints: One immediate way to address the market designer's Question 1 above, and to answer Constrained Stable Matchings more generally, is by brute force. Simply compute every stable matching for a given two-sided market, for example by using the algorithm of Martínez et al. (2004) or that of Bonifacio et al. (2022), and check each against the constraints. While each stable matching can be generated in polynomial time, the number of stable matchings for a given instance can be exponential (Knuth, 1996). So while the above approach will certainly work it may not be feasible in practice. 11 10 We emphasise two features of this example that indicate how our framework is as general as possible. First, preference lists are not complete since worker w 6 is not on the preference list of firm f 3 and vice versa (this is interpreted as both w 6 and f 3 prefer to be unmatched over being matched with the other). Second, the market is unbalanced as there are more positions than workers since there are six positions but only five workers.
11 As we will see later our algorithm that addresses Constrained Stable Matchings spends We will now make an observation regarding lists of constraints. This observation is the first step on the way to reducing the problem of Constrained Stable Matchings to an equivalent but far simpler problem.
The observation is a consequence of the rural hospitals theorem. A constraint requiring that a particular worker be employed at one of a certain number of firms is clearly unsatisfiable if that worker is never employed in any stable matching. The market of Example 1 is unbalanced with more workers than firms, so there will be at least some worker who is unemployed in every stable matching. Indeed we will see that worker w 6 is not employed in any stable matching. Moreover, w 6 appears in the constraint W in (f 2 ) = {w 1 , w 6 } relevant to firm f 2 . However, recall that the interpretation of W in (f 2 ) is that the positions at f 2 must only be filled with those from the list. But since W in (f 2 ) also contains w 1 and f 2 has only one position to fill, this constraint pertaining to market designer's Question 1 is still valid, albeit we Issues with lists of constraints like that described above can always be checked given knowledge of a single stable matching. And a single stable matching can always be found quickly by, for example, a single run of the deferred acceptance algorithm of Gale and Shapley (1962).
In the next subsection we will provide a reduction procedure that uses the above observations to reformulate Constrained Stable Matchings into a far simpler but equivalent formulation.

Reducing Constrained Stable Matchings
The procedure for reducing Constrained Stable Matchings has two main components. The first involves comparing the constraints against a particular stable matching so as to remove constraints concerning participants who do not appear in any stable matching. On occasion this checking procedure will immediately determine if a certain list of constraints renders Constrained Stable Matchings a polynomial amount of time for each generated solution, but of course there may be far fewer solutions with constraints than without. In the absence of any constraints, our algorithm outputs all stable matchings.
infeasible. For example, had the market designer's Question 1 stipulated that F in (w 6 ) was nonempty, then clearly the constraints cannot be satisfied because w 6 is never employed in any stable matching.
The second component involves reducing the many-to-one environment to an equivalent one-to-one environment (by "equivalent" we mean that there is a bijection between the sets of stable matchings for the two environments). This is a standard reduction procedure (see for example Gale and Sotomayor (1985b)). The reason for doing this is that the IDUA procedure is defined only for one-to-one environments, and the IDUA procedure is the key tool in our algorithm. One first runs the IDUA procedure on the equivalent one-to-one environment without constraints. This reduces the unconstrained environment to its normal form -a matching problem that still contains all the essential information and is no larger than the original problem.
The normal form of a one-to-one matching problem is always a balanced market -a market with the same number of workers as positions. Moreover, these are precisely the workers that are employed and the positions that are filled in every stable matching. Importantly for our purposes, this means that the list of constraints specifying Constrained Stable Matchings can be reformulated in terms of a collection of pairs that are to be included and a collection of pairs that are not to be included.
This works as follows. We note that the constraints in Definition 4 are in a sense individual in nature. But with knowledge of the normal form every constraint can be reformulated as a constraint concerning worker-firm pairs. Constraints given by W out (f) and F out (w) are easily handled as they immediately specify pairs that cannot be included in the desired output.
More care must be taken with constraints concerning W in (f) and F in (w). Suppose that a particular worker w and a position at firm f are both included in the normal form (meaning that w is always employed and the position at f is filled in every stable matching). Then a constraint of the form F in (w) = {f} states that the pair (w, f) must be included in any desired stable matching.
Suppose that w and a position at firm f 1 and a position at firm f 2 are all included in the normal form, and there is a constraint of the form F in (w) = {f 1 , f 2 }. This stipulates that w must be employed either at f 1 or f 2 . By definition w cannot be simultaneously employed at both firms, so we cannot simply force the matching to include the pairs (w, f 1 ) and (w, f 2 ). However, we can instead ask if there is a stable matching at which w is not employed at any firm other than f 1 or f 2 . Since w is part of the normal form, this is equivalent to requiring that w is employed at either f 1 or f 2 . Thus the constraint is equivalent to requiring that there is no pair of the form {(w, f k ) : k = 1, 2}.
We have thus shown how we reduce Constrained Stable Matchings to Reduced Constrained Stable Matchings defined as follows.
Reduced Constrained Stable Matchings: Given two disjoint collections of worker-firm pairs C in and C out , is there is a stable matching that includes all worker-firm pairs in C in and does not include any worker-firm pair in C out ? If the answer is yes, generate all such stable matchings.
Before introducing the IDUA procedure (that we postpone until the next section), let us show how to reduce a many-to-one environment to a one-to-one environment.
We first "split" each firm f with q(f) ≥ 2 (i.e., those firms with two or more positions), into q(f) identical copies, f 1 , . . . , f q(f) , such that: (i) all copies of firm f have the same preferences over the set of workers as firm f, and (ii) the q(f) copies of firm f appear in the same order in the preference list of every worker who has firm f on their preference list. Formally, this yields a new one-to-one matching problem where W is a set of m workers, and F is a set of . . , f (q(fn)) n , with preferences inherited as described above. We now convert the many-to-one matching problem of Example 1 into its equivalent one-to-one formulation. This will be our working example throughout.
Reduced Example 1. By splitting firm f 4 into two separate positions, f 1 4 and f 2 4 , the preference lists for each worker and position of the corresponding one-to-one matching problem are presented below, with participants on the other side of the market listed in order of decreasing preference.
In the language of the equivalent one-to-one matching problem, and interpreting constraints as constraints on pairs rather than on on individuals, the market designer would like an answer to: Reduced Question 1. Is there a stable matching that includes at least one of the pairs (w 1 , f 2 ) or (w 6 , f 2 ) and does not include the pair (w 4 , f 1 ) nor the pair (w 6 , f 1 4 ) nor the pair (w 6 , f 2 4 )?
However, applying our reductions above, we know that w 6 is never employed in any stable matching while all other workers are always employed and all positions are always filled. Therefore, the question regarding pairs above can be reformulated as querying whether there is a stable matching in which: Our algorithm works by running queries on the input. Running queries on smaller data sets is typically quicker and particularly so when running multiple queries. Balinski and Ratier (1997) introduced a procedure -termed the Iterated Deletion of Unattractive Alternatives (IDUA) by Gutin et al. (2021) -that reduces a matching problem to its normal form. In essence, the normal form of a matching problem is a matching problem that still contains all the essential information and is no larger than the original problem.
As such our first port of call will be to reduce a matching problem to its normal form. While the IDUA procedure is only defined for the one-to-one environment, we have seen how to convert a many-to-one two-sided matching problem into an equivalent one-to-one environment. But before introducing the IDUA procedure (that we postpone until the Section 3), we will show how to reduce convert a matching problem with assignment constraints using a directed graph formulation that builds on the directed graph formulation of matching problems due to Maffray (1992).

Matching problems with assignment constraints as digraphs 12
Let P be an instance of the one-to-one two-sided matching market. Let W be the set of m workers and let F be the set n of firms in P . (We assume that the reduction from many-to-one to one-to-one has occurred, and so we allow for some firms to be copies of each other.) Given P , we define the associated matching digraph, and only if w is on f's preference list and f is on w's preference list. The arc set A is defined as follows.
We now show how to depict the matching problem with constraints of Example 1 using digraphs. Since there are six workers and four firms, one firm with a quota of two, the matching digraph is a 6 × 5 grid with rows indexed by workers (w 1 through w 6 ) and columns indexed by positions f 1 , f 2 , f 3 , f 1 4 , and f 2 4 . Preferences are depicted by arcs (horizontal for workers and vertical for firms). The matching digraph is depicted in Figure 1, where we note that arcs implied by transitivity have been suppressed for readability.
known as a kernel. 13 Figure 2 shows the two extremal stable matchings for this example. Some vertices are coloured yellow, others are coloured blue, and vertex (5, 4) is a hybrid of yellow and blue. The yellow vertices together with the hybrid vertex make up the workeroptimal stable matching. The blue vertices together with the hybrid vertex make up the firm-optimal stable matching. Each of these matchings is found by running the deferred acceptance algorithm of Gale and Shapley (1962) with the relevant group in the role of proposer. We highlight that neither of these stable matchings satisfy the assignment constraints in Reduced Question 1 since neither contains the required pair (w 1 , f 2 ). That is, neither contain the green vertex of Figure 1. Finally we note that there are no yellow vertices nor blue vertices in the row corresponding to w 6 .
While we have shown how to express a many-to-one two-sided matching problem with constraints using digraphs, we note that the reduced one-to-one two-sided problem may be an unbalanced market (e.g., in our example there are more workers than positions). In the next section we present the IDUA procedure. One useful feature of this procedure is that it will convert the unbalanced market into a balanced market such that only those participants who are matched in every stable matching remain.

The iterated deletion of unattractive alternatives (IDUA)
Since the first step of our algorithm is to run the Iterated Deletion of Unattractive Alternatives procedure (IDUA) we describe it here. Our focus is on how IDUA assists in addressing matching problems with assignment constraints and so we will be brief. For how the procedure works in general, the interested reader may wish to consult Section 2 of Gutin et al. (2021) where the procedure and its interpretation are discussed in greater detail.
We begin by noting that some pairs in a matching problem are not a barrier to stability.
Definition 5. Given a matching digraph D(P ), we define R D(P ) as the subdigraph of D(P ) with the following vertices (and any arcs incident on them) deleted.
(i) If no arc in A F leaves (w, f) ∈ V (D(P )) then delete all vertices (w, Consider part (i) of Definition 5. In words this states that if worker w is the favourite worker of firm f then there cannot be a stable matching in which w is in a matched pair with a firm that w prefers less than f. The reason is that (w, f) would be a blocking pair against any such matching (since w would propose a joint deviation and f would certainly accept). Therefore all firms below f in w's preference list can be removed from consideration by w. We say that such firms are unattractive to w. The firms that w has deemed unattractive will reciprocate by removing w from their preference lists. An analogous statement for firms comes from part (ii) of Definition 5.
The operation described in Definition 5 reduces the size of the matching digraph leaving behind a new smaller matching digraph. Note that there may exist vertices that are not removed by applying R to D(P ), but which will be removed when applying R to R D(P ) . 14 Repeated application of R to D(P ) defines the following iterative procedure.
Definition 6 (The iterated deletion of unattractive alternatives (IDUA)). Given an instance of the matching problem, P , and its associated matching digraph, D(P ) = V, A W ∪A F , define D 0 = D(P ), and for each k ≥ 1, define D k = R(D k−1 ). Finally, define the normal form of P , D * (P ), as D k with minimum k such that D k = R(D k ), i.e., no further reductions will take place for such D k .
Lemma 2 of Gutin et al. (2021) shows that D * (P ) is uniquely defined. This is not immediately obvious and is important to point out as suppose for example we consider part (i) in Definition 5. Clearly there may be multiple vertices satisfying the stipulated condition. Thus Lemma 2 in Gutin et al. (2021) assures the analyst that the order in which vertices satisfying the condition are pivoted around (and hence the order in which other vertices are deleted) will not impact the final outcome.
The following Lemma confirms that while the IDUA procedure can discard information, no "important" information is discarded in the sense that the set of stable matchings for D(P ) can be computed using only the normal form D * (P ).
Lemma 1 (Balinski and Ratier (1997) and Gutin et al. (2021)). The iterated deletion of unattractive alternatives does not change the set of stable matchings. That is, D(P ) and D * (P ) contain exactly the same stable matchings.
Let us now show the effect that running IDUA has on the matching problem of Example 1. In Figure 3 below there are two panels. The left hand panel depicts D(P ) for Example 1 (we note that the image in the left hand panel, panel (a), is the same as that of Figure 1). The right hand panel, panel (b), depicts the normal form, D * (P ). In the interest of space we will not illustrate here how the IDUA procedure incrementally reduced D(P ) to D * (P ). We refer the interested reader to Section 4.2 in Gutin et al. (2021) where the specifics of the IDUA procedure are spelled out.
(1,   We now highlight some observations concerning D * (P ) in panel (b) of Figure 3. First of all, while it is not possible to display all stable matchings on the one image, by comparing the digraph in panel (b) of Figure 3 with the digraph in Figure 2 one can see that the worker-optimal and firm-optimal stable matchings of D(P ) remain in D * (P ). (As indeed they must by Lemma 1.) In fact, the worker-optimal and firm-optimal stable matchings of D(P ) contain exactly the vertices that have no horizontal arcs out of them in D * (P ) and the vertices that have no vertical arcs out of them in D * (P ), respectively (see Lemma 2).
The second thing to note is that there is only one vertex in row 5 and column 4 of D * (P ). This means that worker w 5 is certain to be employed at firm f 4 in every stable matching. This same observation was captured in Figure 2 wherein vertex (5, 4) was a hybrid of the colours yellow and blue indicating that it was in both the worker-optimal stable matching and the firm-optimal stable matching (and hence must be included in every stable matching). Note also that there is no vertex in the row labelled by w 6 of D * (P ). From this we can conclude that all positions are always filled but that worker w 6 is never employed in any stable matching.
A balanced two-sided market is one with the same number of workers as positions. A perfect matching in a balanced two-sided market is one in which every worker is employed and every position is filled. The third and final observation we make regarding panel (b) of Figure 3 concerns balanced markets and perfect stable matchings. While D * (P ) is balanced market, with five workers and five positions, it is also the case that all stable matchings have five workers matched to five positions.
The next two results, Lemma 2 and Lemma 3, show that the observation above on balanced markets and perfect matchings is not an artefact of this specific example. Rather this is a general property of the normal form of every many-to-one two-sided matching market. These results are related to the rural hospitals theorem in the following sense: the rural hospitals theorem assures that once an analyst has found a particular stable matching, µ, the analyst could return to the original problem and discard all market participants who are unmatched in µ. Moreover, all unmatched participants can be removed from the preference lists of those who will be matched. Clearly such an operation would both reduce the size of the problem and ensure a balanced market. Lemma 2 and Lemma 3 provide not only the same assurances of the IDUA procedure but more. Not only can the analyst discard all information pertaining to those who will be unmatched, but the remaining balanced market can quite likely be further reduced by running IDUA on it.
Before stating Lemmas 2 and 3 some additional notation is needed. Let d * ,+ W (x) denote the number of arcs out of x ∈ V (D * (P )) in A W that still remain in D * (P ) and analogously let d * ,+ F (x) denote the number of arcs out of x ∈ V (D * (P )) in A F that still remain in D * (P ). The following result states that the extremal matchings in D * (P ) are precisely the extremal stable matchings in D(P ). 15 Lemma 2 (Gutin et al. (2021)). Let P be an instance of the matching problem.
The following two sets of vertices, M W and M F , are both stable matchings in P .
The next result, whose proof is found in Appendix B, confirms that an analyst studying two-sided matching markets can always confine attention to perfect stable matchings in balanced markets. We emphasise that this holds no matter how unbalanced the original market is and no matter how incomplete preference lists are. As such, any queries concerning the stable matchings of an unbalanced two-sided matching market can be answered by posing the same (reduced) queries of perfect stable matchings in the normal form.
Lemma 3. In D * (P ) there remain r non-empty rows and r non-empty columns (for some r) and all stable matchings in D * (P ) contain r vertices (that is, they are perfect matchings in D * (P )).
When taken together, Lemmas 1 through 3 make a strong case that, for an analyst who views stability as a necessary requirement, the IDUA procedure should be the first port of call when considering any two-sided matching market.

The algorithm
The algorithm of this section solves the following problem. Given D(P ) and disjoint sets V in and V out of vertices of D(P ), return all stable matchings of D(P ), each of which includes all vertices in V in and does not contain any vertex in V out .
For readability the section is split in two. In Subsection 4.1 we state precisely the algorithm that addresses Reduced Constrained Stable Matchings, and we prove its correctness and time complexity. In Subsection 4.2 we give a high level overview of the algorithm by showing how it addresses the market designer's Question 1 concerning the matching problem from Example 1.

The algorithm: in detail
We now state the algorithm. Recall that we assume that the many-to-one environment has been reduced to its equivalent one-to-one formulation.
To find all solutions satisfying the constraints we define a recursive algorithm, Algorithm 2, which is called by our main algorithm, Algorithm 1, defined as follows.
Algorithm 1. The algorithm has 4 steps.
Step 1.2. Let AllSolutions = ∅ and let r be equal to the number of non-empty rows (or columns) in D * (P ).
The following is now the recursive part of the algorithm.
Note that Algorithm 2 is called using the following command: Algorithm 2 (D, V in , V out ), where D, V in and V out make up the input to the algorithm.
Step 2.1. If V in \ V (D) = ∅ then return. For all vertices, (w, f ) ∈ V in , place all vertices, different from (w, f ), in the same row or column as (w, f ) in V out .
Step 2.2. While there is a vertex (w, f ) ∈ V out where d + W ((w, f )) = 0 or d + F ((w, f )) = 0, then modify D by letting it be the digraph obtained by running IDUA on D − (w, f ). Step Step Step 2.5. If M W = M F then add M W to AllSolutions and return.
. Now make the following two recursive calls before returning.
Via Steps 2.6a and 2.6b, Algorithm 2 generates a binary search-tree that can be shown to find all stable matchings satisfying the constraints (whenever one exists). A core idea underlying the algorithm is that if recursive calls are made in Step 2.6, then the stable matching M W will be found in the recursive call made in Step 2.6a and the stable matching M F will be found in the recursive call made in Step 2.6b. Therefore the only time we can possibly return from a call to Algorithm 2 without adding a solution to AllSolutions (in Steps 2.1 or 2.4) is if no solutions exist to our original problem in which case there will be only one call to Algorithm 2 (from Algorithm 1). If M W = M F in Step 2.5, then M W is the unique feasible solution in the current call to Algorithm 2.
In Section 4.2 we will illustrate how the procedure operates in detail by exploring the hypothetical market designer's Reduced Question 1 concerning the market of Example 1.
We will now prove that Algorithm 1 returns all stable matchings containing all pairs in V in and not containing any pairs in V out in polynomial time per solution. We first prove the correctness of the algorithm before proving its time complexity. For both results we will need the following Lemma whose proof is in Appendix B.
Lemma 4. Let D i be any digraph obtained by running IDUA on some instance of the one-to-one two-sided matching market. Assume that D i has r rows and columns (and therefore all stable matchings are perfect matchings of size r).
And every stable matching in D i − v of size r is a stable matching in D i not containing v.
Armed with Lemma 4 we can now state the main theorem whose proof is found in Appendix B. We conclude this section by recalling that if a stable matching satisfying the constraints stipulated by Reduced Constrained Stable Matchings exists, then Algorithm 1 will not only confirm this fact but will also output all such stable matchings. However, it is possible that a market designer would be content with a single stable matching satisfying the constraints. If so, it is straightforward to modify the algorithm in order to output either the worker-optimal stable matching satisfying the constraints or the firm-optimal stable matching satisfying the constraints. One just has to output M W or M F in the very first call to Algorithm 2 instead of making recursive calls in Step 2.6.

The algorithm: an example
Let us now illustrate how the algorithm works. To do so we use the two-sided market from Example 1 and the market designer's Question 1 pertaining to it.
The input to Algorithm 1 will be the preference lists from Reduced Example 1 that, after the reduction to the one-to-one environment has been performed, is equivalent to the digraph D(P ) in Figure 1. The variant of Reduced Constrained Stable Matchings submitted to Algorithm 2 is the Reduced Question 1 that is to decide if there exists a stable matching in D(P ) containing the vertex (w 1 , f 2 ) and also avoiding the vertex (w 4 , f 1 ). The output will be the empty set if there is no such stable matching and all such stable matchings whenever one exists.
Step 1.1 of Algorithm 1 requires running IDUA. This was already depicted in Figure 3. The colour coding of vertices is as follows: vertices are coloured green if they are required to be in the stable matching and coloured red if required not to be. Once the IDUA procedure is complete so that the normal form D * (P ) has been arrived at, Algorithm 1 then calls Algorithm 2.
The first step of Algorithm 2, Step 2.1, makes two stipulations. In the first, it checks if any of the green vertices were deleted when applying IDUA. If so, then there is no stable matching satisfying the requirements. If this occurs Algorithm 2 exits and Algorithm 1 proceeds. Note that upon running IDUA for the example, vertex (1, 2), in D(P ) in the left hand panel of Figure 3 remains in D * (P ) in the right hand panel. We observe that two of the red vertices, vertices (6, 4) and (6, 5), that were required not to be part of a desired stable matching are no longer present in D * (P ) in the right hand panel of Figure 3. This is not a problem. This simply confirms that these vertices are not part of any stable matching, and so a constraint requiring that neither be contained in a particular stable matching is rendered redundant. To say it another way, if red vertices are deleted in going from D(P ) to D * (P ) the algorithm proceeds unaffected.
The second stipulation of Step 2.1 converts all queries about required pairs (green vertices) into corresponding queries about avoided pairs (red vertices). Since the green vertex, (1, 2), remains after applying IDUA, Lemma 3 confirms that worker w 1 is employed in every stable matching and that the single position at f 2 is filled in every stable matching. But given this, the query about worker w 1 being employed at firm f 2 can be converted into a collection of equivalent queries about worker w 1 not being employed by any firm other than f 2 and firm f 2 's position not being filled by any worker other than w 1 . If there exists a stable matching that avoids all these constraints then such a matching must contain the pair (w 1 , f 2 ).
Thus the problem of determining if there exists a stable matching in which worker w 1 is employed at firm f 2 is equivalent to determining if there is a stable matching in the normal form that does not include vertices (1, 1), (1, 3), (1, 5) and vertices (2, 2), (3, 2), (4, 2), where the first collection of three vertices require that w 1 must not be employed at f 1 , f 3 , or f 5 and the second collection of three vertices require that the position at f 2 is not filled by w 2 , w 3 , or w 4 . Panel (a) in Figure 4 below displays the result of converting the query about the required (green) vertex (1, 2) in D * (P ), shown in panel (b) of Figure 3, to an analogous query about (red) vertices being avoided in D * (P ).
Step 2.2 is one of the key steps. It states that whenever there is a red vertex with either horizontal out-degree zero or vertical out-degree zero, that this vertex should be deleted from the digraph and the IDUA procedure should be run on the subdigraph that remains. The vertices satisfying this requirement can be seen in panel (a) of Figure 4. They are (1, 1), (2, 2), (1, 5), (3, 2), and (4, 1), where the first two vertices have horizontal out-degree equal to zero and the latter three vertices have vertical out-degree equal to zero. We note that not all red vertices can be instantly deleted at Step 2.2. For example, from panel (a) of Figure 4 it clear that neither vertex (1, 3) nor vertex (4, 2) satisfy the requirement as both have positive horizontal out-degree and positive vertical out-degree. We emphasise this point strongly as in this particular example the end result would be the same had we run IDUA on procedure on D * − V out . But it is important to note that vertices (1, 3) and (4, 2) were removed by the IDUA procedure applied to the reduced subdigraph and were  not deleted in advance of the procedure. In Appendix C we present an example where deleting all vertices in V out and then applying IDUA yields an incorrect conclusion. To see why vertices with either horizontal out-degree zero or vertical out-degree zero can be deleted, let us consider vertex (1, 1) with horizontal out-degree zero. Invoking Lemma 4 we can be sure that every stable matching in D * (P ) not containing vertex (1, 1) is a stable matching in D * (P ) − (1, 1). Moreover, if the stable matchings in D * (P )−(1, 1) are the same size as the stable matchings of D * (P ), then every stable matching in D * (P )−(1, 1) is a stable matching in D * (P ) that does not include (1, 1). Given that we are to avoid the vertex (1, 1), we can run IDUA on D * (P ) − (1, 1). Intuitively the reason this works is as follows. As (1, 1) has horizontal out-degree of zero, firm f 1 is worker w 1 's most preferred worker. As we have already run IDUA on the digraph this implies that (1, 1) has no vertical arc into it, as if it did the in-neighbour would have been removed by the IDUA procedure. Therefore (1, 1) will not be a blocking pair for a stable matching in D * (P ) − (1, 1) (of size r) as f 1 will be matched with some worker, w i , and (1, 1) will have an arc into this pair (i, 1).
Panel (b) of Figure 4 depicts the result of Step 2.2 of Algorithm 2.
Step 2.2 specifies that in turn, each of the vertices in V out with out-degree zero was deleted and then IDUA was run on what remains. By definition there can be no red vertices with out-degree zero remaining. (Though we recall that red vertices with positive out-degree could in theory remain, albeit none did in this example). Moreover, this step can also delete other vertices. For example, in going from panel (a) to panel (b) in Figure 4, we note that red vertices (1, 3) and (4, 2) and the non-red vertex (2, 3) were all deleted by Step 2.2. Note that the order in which we delete red vertices satisfying the requirement of Step 2.2 and then apply IDUA will not impact the final outcome due the correctness of Algorithm 2 proved in Theorem 1. Indeed, in the proof we show that an arbitrary order will lead to a correct outcome.
Step 2.3 now collects the worker-optimal pairs for every worker, M W , and the firm-optimal pairs for every firm, M F . Step 2.4 checks to see that both M W and M F are the size of a stable matching. If not, then there cannot be a stable matching satisfying the constraints and the Algorithm states as much. If both M W and M F are the size of a stable matching, then Step 2.5 checks to see if they are one and the same. If they are, that is if M W = M F , then there is exactly one stable matching satisfying the constraints and the algorithm returns it.
If M W = M F , then we can make two observations. First, there are multiple (at least two) stable matchings satisfying the constraints. Second, it must be that M W (M F ) is the worker-optimal (firm-optimal) stable matching satisfying the constraints. For the market of Reduced Example 1 we depict M W and M F in Figure 5 below. We adopt the same colour coding as that in Figure 2. That is, vertices solely in the worker-optimal stable matching satisfying the constraints are coloured yellow, vertices solely in the firm-optimal stable matching satisfying the constraints are coloured blue, and vertices in both are coloured a hybrid of yellow and blue.
Since M W = M F , as seen in Figure 5, then Step 2.6 of the algorithm is called. The first thing this step does is to identify a vertex, (w, f), that is contained in M W but not in M F . (Given that M W = M F there must be at least one such vertex.) We now run the recursive Algorithm 2 on two subcases: one where (w, f) is required to (1, 2) (2, 1) (2, 5) (3, 1) (3, 3) (3, 5) (4, 3) (4, 5) (5, 4) Figure 5: The two extremal stable matchings satisfying the constraints.
be included (so that (w, f) is added to V in ) and the other where it is required not to be included (and hence (w, f) is part of V out ). As can be seen from Figure 5, the first vertex we encounter of this form is the vertex (2, 1). Thus we now run Algorithm 2 on (D, V in ∪ (2, 1), V out ) and on (D, V in , V out ∪ (2, 1)). Note for the first of these cases, requiring that (2, 1) be included is equivalent to requiring that (2, 5) and (3, 1) are not included. This repeated splitting into two subcases generates a binary search-tree that we depict in Figure 6. There are five pairs of panels in Figure 6 labelled (a) through (e). In every pair of panels, the left panel depicts the temporary constraints while the right hand panel depicts the extremal matchings associated with the temporary constraints.
The first pair of panels in Figure 6, labelled (a), depicts the first time that Step 2.6 of Algorithm 2 is called. The left-hand panel reproduces panel (b) from Figure 4 while the right hand panel reproduces Figure 5. While there is nothing new depicted (a) in these two panels, we include them to emphasise that this is the starting point of the recursive part of the algorithm. From this point, the procedure "splits" indicated by the two thick black arrows from the top row to the second row -one going "left" to the panels labelled (b) and the other going "right" to the panels labelled (c).
Let us first consider the two adjoining panels in (b). Note that in addition to vertex (1, 2) being required, it is now also the case that vertex (2, 1) is required. This is indicated by colouring vertex (2, 1) green in the left panel. Given that vertex (2, 1) is required, it must be that vertices (2, 5) and (3, 1) cannot be simultaneously part of the stable matching (this is simply applying Step 2.1 to this subcase). As such (2, 5) and (3, 1) are coloured red. Contrast this with the left panel of (c). Here we note that vertex is (2, 1) is coloured red, indicating that it cannot be included. In other words, (b) begins the part of the search tree where (1, 2) is required to be included and (2, 1) is required to be included; while (c) begins the part of the search tree where (1, 2) is required to be included and (2, 1) is required not to be included.
The same is not true of the right hand panel of (b). Note that here there remains an anti-clockwise cycle involving vertices {(3, 3), (4, 3), (4, 5), (3, 5)}. As shown in Theorem 1 of Gutin et al. (2021), it is cycles in the normal form that are the barrier to uniqueness. So it must be that there are at least two stable matchings satisfying the current constraints in this branch of the subtree. Indeed this is true and is indicated by the fact that in the right hand panel of (b), M W = M F . Therefore, one more split is required. The vertex that is pivoted around this time is (3, 3). In the left hand panel of (d), this vertex is coloured green indicating it must be included, while in the left hand panel of (e) this vertex is coloured red indicating it must not be included.
We conclude by noting that the algorithm identifies three stable matchings for the market of Reduced Example 1 that accord with the hypothetical market designer's participation constraints as stipulated by Reduced Question 1. In order of decreasing worker preference, these three stable matchings are: 2), (2, 1), (3, 3), (4, 5), (5, 4)} M * 2 = {(1, 2), (2, 1), (3, 5), (4, 3), (5, 4)} M * 3 = {(1, 2), (2, 5), (3, 1), (4, 3), (5, 4)} As such, the market designer's Question 1 concerning the many-to-one matching market of Example 1 is answered in the affirmative with the three stable matchings satisfying the assignment constraints given by: For an arc xy the first vertex x is its tail and the second vertex y is its head. Moreover, x is called an in-neighbour of y and y an out-neighbour of x. We also say that the arc xy leaves x and enters y. We say that a vertex x is incident to an arc a if x is the head or tail of a. For a vertex v ∈ V (D), the out-degree of v in D, is a sequence of vertices x 1 , x 2 , . . . , x p for which there is an arc from each vertex in the sequence to its successor in the sequence. Such a walk is written as W = x 1 x 2 . . . x p . Special cases of walks are paths and cycles. A walk W is a path if the vertices of W are distinct. If the vertices x 1 , x 2 , . . . , x p−1 are distinct, for p ≥ 2 and x 1 = x k , then W is a cycle.
For a digraph D = (V, A) and an arc xy ∈ A, deletion of xy from D results in the B Proofs omitted from the main text Lemma 3. In D * (P ) there remain r non-empty rows and r non-empty columns (for some r) and all stable matchings in D * (P ) contain r vertices (that is, they are perfect matchings in D * (P )).
Proof. Let r W denote the number of non-empty rows in D * (P ) and let r F denote the number of non-empty columns in D * (P ). By Lemma 2 we note that M W is a stable matching with r W elements and M F is a stable matching with r F elements. As every stable matching contains equally many elements we must have r W = r F and all stable matchings contain r F (= r W ) elements, completing the proof.
Lemma 4. Let D i be any digraph obtained by running IDUA on some instance of the one-to-one two-sided matching market. Assume that D i has r rows and columns (and therefore all stable matchings are perfect matchings of size r).
And every stable matching in D i − v of size r is a stable matching in D i not containing v.
Proof. Let v ∈ V (D i ) be arbitrary, such that d + W,i (v) = 0 or d + F,i (v) = 0 in D i . Without loss of generality assume that d + W,i (v) = 0. Assume that M is a stable matching in D i − v of size r. We will first show that M is a stable matching in D i not containing v.
Clearly v ∈ M as v ∈ D i − v, so it suffices to show that M is a stable matching in D i . As d + W,i (v) = 0 in D i we note that v can have no arcs into it in D i from A F (as D i is a digraph obtained by running IDUA on some instance). So, if v = (w, f) and w = (w , f) ∈ M (w must exist as the size of M is r) then vw ∈ A(D i ). This implies that v is not a blocking edge for M in D i . As no vertex in D i − v is a blocking edge for M in D i (as they are not blocking edges for M in D i − v) we note that M is indeed a stable matching in D i .
Conversely assume that M is a stable matching in D i not containing v. Then clearly M is also a stable matching in D i −v as no vertex in D i is blocking for M . Proof. By Lemma 1 the digraph D * (P ) used in the call to Algorithm 2 in Step 1.3 will contain exactly the same stable matchings as D(P ). So, if Algorithm 2 adds all the desired stable matchings to AllSolutions in the desired time, then Theorem 1 holds. We will now prove this.
Clearly if V in \ V (D * ) = ∅ holds in Step 2.1, then there can be no solution in D containing all the vertices in V in , so the algorithm correctly returns without adding anything to AllSolutions. Furthermore, as all solutions with (w, f ) in the solution contain no vertices different from (w, f ), in the same row or column as (w, f ), we note that the second part of Step 2.1 does not change which solutions satisfy the constraints.
By Lemma 1 and Lemma 4 we note that every operation in Step 2.2 maintains the same set of feasible solutions.
By Lemma 2 we note that both M W and M F defined in Step 2.3 are stable matchings in D. As (w, f ) ∈ V out for all (w, f ) ∈ V (D) where d + W ((w, f )) = 0 or d + F ((w, f )) = 0 we furthermore note that neither M W or M F contain any vertices from V out . If |M W | = r (which is equivalent to |M F | = r as |M W | = |M F |) then by the operation in Step 2.1 we note that all vertices in V in belong to both M W and M F (as no vertices from the rows or columns containing vertices in V in belong to M W or M F ). So if |M W | = r then both M W and M F are stable matchings satisfying the constraints.
If |M W | < r in Step 2.4, then clearly there is no stable matching in D of size r, which implies that there is no stable matching can be added to AllSolutions (as all solutions in AllSolutions must have size r, by Step 1.2 and Lemma 3). So if we return in Step 2.4, then there is indeed no desired solution in D.
If Algorithm 2 does not return at Step 2.4, we can be sure that the digraph D being considered at Step 2.5 has both |M W | = r and |M F | = r, where r is the size of a stable matching. If M W = M F in Step 2.5, then M W is the unique solution in D.
We know this to be the case by appealing to Lemma 3 and Theorem 1 in Gutin et al. (2021). That is, Lemma 3 in Gutin et al. (2021) confirms that both M W and M F are always perfect stable matchings of size r in the normal form, and Theorem 1 in Gutin et al. (2021) shows that if M W = M F then there is a unique stable matching of size r in the normal form. In Step 2.6 we note that every solution in D that satisfies the constraints will be found in the recursive call in Step 2.6a if (w, f ) belongs to the solution and it will be found in the recursive call in Step 2.6b if (w, f ) does not belongs to the solution. So every solution will be found in one of the recursive calls. Furthermore we note that no solution can be found in both the recursive calls in Step 2.6 as the solution either contains (w, f ) or it does not. Therefore all solutions will be found and no solution will be found more than once. This proves the correctness of the algorithm.
We will now prove the time complexity. We note that all steps, that do not involve a call to Algorithm 2, in Algorithm 1 and in Algorithm 2 can be performed in polynomial time. This is not difficult to see as IDUA runs in polynomial time and in Step 2.2 we cannot delete more than a polynomial number of vertices. We will now show that the number of calls to Algorithm 2 is bounded by 2s + 1, where s is the total number of feasible solutions outputted by Algorithm 1.
Consider the binary search tree, T , where every node corresponds to a call to Algorithm 2 and the root corresponds to the very first call to Algorithm 2. If we from an iteration of Algorithm 2, corresponding to node x in T , make two recursive calls in Step 2.6 then the two nodes corresponding to these two calls will be the two children of x in the search tree. And if the iteration returns in Steps 2.1, 2.4 or 2.5 then x is a leaf of the tree. Therefore every node of the tree either has two children or none (i.e., it is a leaf). Let l denote the number of leaves in T . It is well-known (and can be shown by induction) that |V (T )| ≤ 2l − 1 (this is true if |V (T )| = l = 1 and if |V (T )| > 1 we can use induction on the two subtrees of the root).
As the stable matching M W will be found in the recursive call made in Step 2.6a and the stable matching M F will be found in the recursive call made in Step 2.6b we note that the only way a call to Algorithm 2 won't produce a solution is if it is made from Algorithm 1. Therefore every leaf, apart from possibly the root, will add a solution to AllSolutions. Therefore the following holds.
|V (T )| ≤ 2l − 1 ≤ 2(s + 1) − 1 = 2s + 1 As |V (T )| is the number of calls to Algorithm 2 and s was the total number of feasible solutions returned, we note that we perform a polynomial amount of work per solution found (if there is no solution we also perform a polynomial amount of work). This completes the proof.
In fact if V out = {(3, 1)} then we note that M (the white vertices in Figure 7) is a stable matching in D − (3, 1), but M is not a stable matching in D avoiding (3, 1), which is why we can only delete vertices with no horizontal arcs out of them or vertices with no vertical arcs out of them in Step 2.2 of our algorithm. This also illustrataes why we need the condition d + W,i (v) = 0 (or d + F,i (v) = 0) in Lemma 4.