{'fraction_non_alphanumeric': 0.038672654690618764, 'fraction_numerical': 0.009481037924151697, 'mean_word_length': 3.9987528580336726, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Disjoint Stable Matchings in Linear Time

We show that given a SM instance G as input we can find a largest collection of pairwise edge-disjoint stable matchings of G in time linear in the input size. This extends two classical results: 1. The Gale-Shapley algorithm, which can find at most two ("extreme") pairwise edge-disjoint stable matchings of G in linear time, and 2. The polynomial-time algorithm for finding a largest collection of pairwise edge-disjoint perfect matchings (without the stability requirement) in a bipartite graph, obtained by combining K\"{o}nig's characterization with Tutte's f-factor algorithm. Moreover, we also give an algorithm to enumerate all maximum-length chains of disjoint stable matchings in the lattice of stable matchings of a given instance. This algorithm takes time polynomial in the input size for enumerating each chain. We also derive the expected number of such chains in a random instance of Stable Matching.


Introduction
All our graphs are finite, undirected, and simple. We use V (G), E(G) to denote the vertex and edge sets of a graph G, respectively. A matching in a graph G is any subset M ⊆ E(G) of edges of G such that no two edges in M have a common end-vertex. An input instance of the Stable Matching problem contains a bipartite graph G with the vertex partition V (G) = M ⊎ W where the two sides M, W are customarily called "the set of men" and "the set of women", respectively. Each woman has a strictly ordered preference list containing her neighbors-a woman prefers to be matched with a man who comes earlier in her list, than with one who comes later-and each man similarly has a strictly ordered preference list containing all his neighbors.
Definition 1 (Blocking pair). A man-woman pair (m, w) ∈ E is said to be a blocking pair with respect to a matching M of G if both m and w prefer each other over their matched partner in M .
Definition 2 (Stable matching). A matching M of G is said to be stable if there is no blocking pair in G with respect to M .
A matching M that is not stable is said to be unstable. The Stable Matching instance consists of a bipartite graph G with vertex partition M ⊎ W and the associated preference lists. The Stable Matching problem involves deciding if G has a stable matching, and outputting one if it exists.
The Stable Matching problem models a number of real-world applications where two disjoint sets of entities-fresh graduates and intern positions; students and hostel rooms; internet users and CDN servers; and so on-need to be matched based on strict preferences. Gale and Shapley famously proved that every instance of Stable Matching indeed has a stable matching, and that one such matching can be found in linear time [3]. The Gale-Shapley algorithm for Stable Matching follows a simple-almost simplistic-greedy strategy: in turn, each unmatched man proposes to the most preferred woman who has not rejected him so far, and each woman holds on to the best proposal (as per her preference) that she has got so far. Gale and Shapley proved that this algorithm invariably finds a stable matching, which is said to be a man-optimal stable matching. Of course, the algorithm also works if the women do the proposing; a stable matching found this way is said to be woman-optimal.
It is not difficult to come up with instances of Stable Matching where the man-optimal and women-optimal stable matchings are identical, as also instances where they differ. A rich theory about the combinatorial structure of stable matchings has been developed over the years. In particular, it is known that the set of all stable matchings of a Stable Matching instance forms a distributive lattice under a certain natural partial order, and that the woman-optimal and man-optimal stable matchings form the maximum and minimum elements of this lattice. It follows that each instance has exactly one man-optimal stable matching and one woman-optimal stable matching, and that if these two matchings are identical, then the instance has exactly one stable matching in total.
The Gale-Shapley algorithm can thus do a restricted form of counting stable matchings: it can correctly report that an instance has exactly one stable matching, or that it has at least two, in which case it can output two different stable matchings. The maximum number of stable matchings that an instance can have has also received quite a bit of attention. Irving and Leather [6] discovered a method for constructing instances with exponentially-many stable matchings; these instances with n men and n women have Ω(2.28 n ) stable matchings. This is the current best lower bound on the maximum number of stable matchings. After a series of improvements, the current best upper bound on this number is O(c n ) for some constant c [8,15].
Our focus in this work is on finding a large collection of pairwise edge-disjoint stable matchings:

Disjoint Stable Matchings
Input: A Stable Matching instance G and an integer k. Task: Decide if G has at least k pairwise disjoint stable matchings, and output such a collection of stable matchings if it exists.
Finding such a collection of disjoint stable matchings is clearly useful in situations which involve repeated assignments. For instance, when assigning people to tasks-drivers to bus routes, medical professionals to wards, cleaning staff to locations-this helps in avoiding monotony without losing stability. As another example, consider a business school program which has a series of projects on which the students are supposed to work in teams of two. Using a different stable matching from a disjoint collection to pair up students for each project will help with their collaborative skills while still avoiding problems of instability.
Even in those cases where only one stable matching suffices-such as when assigning medical students to hospitals once a year-a disjoint collection can still be very useful. Given such a collection, an administrator in charge of deciding the residencies can evaluate each stable matching based on other relevant considerations-such as gender or racial diversity, or costs of relocation-to choose an assignment which optimizes these other factors while still being stable.
Our main result is that Disjoint Stable Matchings can be solved in linear time: Theorem 1. There is an algorithm which takes an instance G of Stable Matching, runs in time linear in the size of the input, and outputs a pairwise disjoint collection of stable matchings of G of the largest size.
This immediately yields: Corollary 1. Disjoint Stable Matchings can be solved in linear time.
To the best of our knowledge there is no published work about finding disjoint stable matchings. Finding disjoint matchings (without the stability requirement) has received a lot of attention over the years, and a number of structural and algorithmic results are known [14,1,12]; we mention just one, for perfect matchings in bipartite graphs.
Observe that a bipartite graph G has a perfect matching only if both sides have the same size, say n. Also, any collection of pairwise disjoint perfect matchings of such a graph G can have size at most n. This is because deleting the edges of one perfect matching from G decrements the degree of each vertex by exactly one, and the maximum degree of G is not more than n. A graph is said to be k-regular if each of its vertices has degree exactly k. König proved that a bipartite graph G contains k pairwise edge-disjoint perfect matchings if and only if G has a k-regular subgraph [10]. Tutte's polynomial-time algorithm for finding the so-called f -factors [18] can be used to find a k-regular subgraph of G. Putting these together we get a polynomial-time algorithm for finding a largest collection of edge-disjoint perfect matchings in bipartite graphs.
In stark contrast, checking if a non-bipartite graph has two disjoint perfect matchings is already NP-hard even in 3-regular graphs [5,2].
Relation to lattice structure. It is known that the set of stable matchings in a given instance forms a distributive lattice [9]. We show that there is always a solution to Disjoint Stable Matchings that is a chain in this lattice. We give an algorithm to enumerate all the chains of disjoint stable matchings. The algorithm takes time polynomial in the size of the input for outputting each such chain. We also show that the expected number of such chains in a random instance is at most quasi-polynomial with high probability.

Preliminaries
We recall the Gale-Shapley algorithm and the lattice structure of stable matchings here for the sake of completeness. The classical Gale-Shapley algorithm [4, Figure 1.3] solves the Stable Matching problem by a deferred acceptance mechanism. Each man proposes the women on his list in decreasing order of preference until some woman accepts his proposal. A woman w accepts a proposal from a man m if either w is unmatched or she prefers m over her current partner. The extended version of the Gale-Shapley algorithm (Algorithm 1) [4, Figure 1.7] reduces the preference lists by eliminating certain pairs that do not belong to any stable matching. By deleting a (man-woman) pair (m, w), we mean deleting m from w's preference list and w from that of m.

Algorithm 1 Extended Gale-Shapley
assign each person to be free 3: while some man m is free do 4: w ← first woman on m's list 5: if some man p is engaged to w then 6: assign p to be free 7: end if 8: assign m and w to be engaged to each other 9: for each successor m ′ of m on w's list do 10: delete w on m ′ 's list 11: delete m ′ on w's list ⊲ deleting the pair (m ′ , w) 12: end for 13: end while return Stable matching consisting of n engaged pairs 14: end procedure The algorithm terminates when every man is engaged or has exhausted his preference list. When the algorithm ends, the resulting modified preference list is a reduced list. Furthermore, it can be easily verified that, on termination, each man is either unmatched or is engaged to the first woman in his reduced preference list, and each woman is either unmatched or is engaged to the last man in hers. These engaged pairs constitute a man-optimal stable matching. It is known that every stable matching leaves the same set of people unmatched [4].
For a given stable marriage instance we will refer to the final preference lists generated by GS-Extended, with men as proposers, as man-oriented Gale-Shapley lists, or MGS-lists. The final preference lists generated by this algorithm when women do the proposing are called WGS-lists. Finally, if we take for each person the intersection of their MGS-list and WGS-list, we get the GS-list. It is known that the GS-lists can be obtained by first applying man-oriented GS-Extended to get MGS-lists and then, starting with the MGS-lists, applying woman-oriented GS-Extended [4].
Let G GS−list be the graph obtained from the GS-lists as follows: Each man m i is represented by a vertex m i and each woman w i is represented by a vertex w i , and an edge (m i , w i ) is present if and only if m i is in w i 's preference list in the GS-lists. We say that a matching M is contained in the GS-lists if M is a matching in G GS−list .
The next theorem summarizes some useful properties of GS-lists. 1. all stable matchings are contained in the GS-lists; 2. no matching (stable or otherwise) contained in the GS-lists can be blocked by a pair that is not in the GS-lists; 3. In the man-optimal (respectively woman-optimal) stable matching, each man is partnered by the first (respectively last) woman on his GS-list, and each woman by the last (respectively first) man on hers.
Lattice structure of stable matchings. We need the following results about the lattice structure of stable matchings [4]. For a given stable marriage instance, a dominance relation on stable matchings is defined as follows:  With the help of the above lemmas, it is easy to see that the set of all stable matchings forms a distributive lattice and the man-optimal matching and the woman-optimal matching represent the minimum and maximum elements of the lattice [4, Theorem 1.

Finding Disjoint Stable Matchings
In this section we describe and analyze our algorithm for finding a largest collection of disjoint stable matchings in a given instance of Stable Matching.
Given a stable marriage instance, two matchings M 1 and M 2 are said to be disjoint stable matchings if both M 1 and M 2 are stable and they do not share a common edge. Throughout this section, we denote the man-optimal and woman-optimal stable matchings by M o and M z respectively. First, we would like to know if there exists a stable marriage instance which has at least two disjoint stable matchings. The following example of a stable marriage instance shows the existence of disjoint stable matchings.  It can be easily verified that the above marriage instance has three (and only three) disjoint matchings as given below. The following lemma gives a necessary condition for the existence of two or more disjoint stable matchings for a given marriage instance. The algorithm first finds the man-optimal and woman-optimal stable matchings (M o and M z respectively) by executing GS-Extended. If these matchings share an edge, the algorithm stops. Otherwise it modifies the instance by deleting all the edges that appear in M o . It then computes a man-optimal matching M ′ of the new instance using GS-Extended. If M ′ is disjoint from the womanoptimal matching M z then it deletes the edges of M ′ from the instance. The algorithm repeats this procedure as long as GS-Extended keeps returning a stable matching which is disjoint from M z . It stores all the M z -disjoint matchings obtained during this process in a set S. We note that this is a stronger version of the BreakMarriage algorithm of McVitie and Wilson [13].

Algorithm 2 Disjoint Stable Matchings
Input : A stable matching instance G Output: A maximum size set S of disjoint stable matchings. 1: procedure Disjoint stable matchings(G) 2: S ← ∅ 3: Mz ←StableMatching(G, woman-optimal) ⊲ Woman-proposing GS Algorithm 4:   Proof. Each iteration of the algorithm modifies the given instance by deleting the edges of the matching constructed. Let the instance considered at the beginning of iteration i be G i . Thus G 1 = G. Since M i is constructed by executing the extended Gale-Shapley algorithm on the instance G i , it follows that M i is the man-optimal matching in G i . Further, all the men get strictly better partners in M i compared to M j , j > i and all the women get strictly worse partners in M i compared to M j , for j > i.

⊓ ⊔
We now show that among all the chains of disjoint stable matchings, the one output by Algorithm 2 is a longest chain. Lemma 6. Algorithm 2 outputs a longest chain of disjoint stable matchings.
Proof. Let C : M o = M 1 ≺ M 2 ≺ · · · ≺ M k be the chain of disjoint matchings obtained by running Algorithm 2. For the sake of contradiction, let C ′′ : We know that M 2 dominates all the stable matchings which are disjoint with M 1 . Matching M ′ 2 cannot be disjoint with M 2 , as otherwise, we can get a longer chain Therefore we can replace M ′ 2 with M 2 to get another chain of disjoint stable matchings M 1 ≺ M 2 ≺ M ′ 3 ≺ · · · ≺ M ′ ℓ of length ℓ.
In this way, we successively replace each M ′ i of the chain C ′′ with M i from the chain C to get the ℓ-length chain M 1 ≺ M 2 ≺ . . . M k ≺ M ′ k+1 ≺ · · · ≺ M ′ ℓ of disjoint stable matchings. But this implies that there exists a stable matching M ′ k+1 which satisfies the strict relation M k ≺ M ′ k+1 , which is a contradiction since M k has non zero interection with the woman-optimal matching M z .

⊓ ⊔
We have shown that among all the chains of disjoint stable matchings, the one output by Algorithm 2 is of maximum length. We still need to prove that there is no larger set of disjoint stable matchings which is possibly not a chain. We use the following result due to Teo and Sethuraman to show that any such set of disjoint stable matchings has a corresponding chain of disjoint stable matchings. Moreover, the length of this chain is same as the size of the set.

Enumerating all max-length Chains
Algorithm 2 gives one maximum-length chain of disjoint stable matchings. It is an interesting question whether such a chain is unique. The example in Figure 3 shows that there can be multiple maximum-length chains of disjoint stable matchings.
We now give an algorithm to enumerate all such chains with polynomial delay. For the enumeration, we exploit the lattice structure of stable matchings described in Section 2.
The #P -hardness of counting all the maximum-length chains can be easily deduced from the #P -hardness of counting all the stable matchings in a given instance [7]. For a given instance G, if we construct a new instance G ′ by adding a new man-woman pair (m, w) such that both prefer each other over all the others, then every stable matching in G ′ contains the pair (m, w). Hence the length of a maximum-length chain of disjoint stable matchings is 1, and each stable matching in the given instance is such a chain.
Algorithm 3 describes the enumeration procedure. We need some notation and definitions. Let A 0 be the man-optimal matching. Define the set A = that is, B i is the greatest lower bound of the set of all the stable matchings which strictly dominate B i−1 . We note that A and B are the chains returned by Algorithm 2 with man-proposing and woman-proposing versions respectively. Since both are maximum-length chains of disjoint stable matchings, t = k. m1 w4 w1 w3 w2 w1 m2 m1 m3 m4 m2 w4 w2 w3 w1 w2 m1 m3 m2 m4 m3 w1 w3 w2 w4 w3 m4 m2 m3 m1 m4 w1 w4 w2 w3 w4 m3 m4 m2 m1 Let X = {X 0 , · · · X k } be a maximum-length chain of disjoint stable matchings i.e. X 0 ≺ X 1 ≺ · · · ≺ X k . We note the following property of the matchings in X.
. Therefore X i+1 is strictly dominated by A i . Since A i+1 is the greatest lower bound of all such stable matchings which are strictly dominated by is also a maximum chain of disjoint stable matchings given that A j X j B k−j for 0 ≤ j ≤ i.
Outline of the algorithm: An algorithm to enumerating all the stable matchings in a given instance is known in literature [4, Section 3.5]. We use this result to construct the sublattice L of all the stable matchings N which are in between two matchings M and M ′ (i.e. M N M ′ ), where M, M ′ are any two stable matchings such that M M ′ . To construct the sub-lattice L, we construct a new instance as follows: 1. Delete every woman in m's list better than his partner in M and worse than his partner in M ′ . Delete every man in w's list better than her partner in M ′ and worse than her partner in M .
2. Update the preference list so that m is in w's list iff w is in m's list.
In the new instance, M and M ′ are man-optimal and woman-optimal matchings respectively. The set of stable matchings in this instance is precisely L, which can be enumerated by the algorithm for enumeration of stable matchings. In Algorithm 3, we first compute the sublattice L 0 between A 0 and B k . Then we recursively call Algorithm 3 for every X 0 ∈ L. From Corollary 3 we know that given a partial list X 0 , X 1 . . . , X i of disjoint stable matchings, we can find the next matching in the chain. The algorithm first finds the man-optimal matching Y i+1 after deleting X i from the given instance. In Algorithm 3, this method is referred to as NextBestDisjointMatching. Then it constructs the sub-lattice α Yi+1 between Y i+1 and B k−(i+1) . Now, for every stable matching M in α Yi+1 , it appends the input list as X 0 , X 1 . . . , X i , M and recursively calls itself to extend each list further. The correctness of the algorithm can be seen from the fact that it picks exactly one stable matching from each of the k sublattices, and they are disjoint by construction. Fig. 4: For every matching X i in the sub-lattice L i , the algorithm finds the next best matching Y i+1 in L i+1 . It then constructs the sub-lattice α Yi+1 between Y i+1 and B k−(i+1) and appends the input list with every X (i+1) in α Yi+1 Lemma 8. Algorithm 3 terminates in O(n 3 + n 2 (|L| + |P |)) time, where P is the set of maximum-length chains of disjoint stable matchings and L is the set of all stable matchings featuring in the enumeration.
Therefore, as the set mentioned above is unique given M , Thus, the total time complexity for line 6 to line 10 is Printing the output would take M ax(|L|, |P |) time.

⊓ ⊔
We analyze the number of maximum-length chains of disjoint stable matchings in a random stable matchings instance with complete lists. Given a natural number n, we create a random stable matchings instance of n men and n women by assigning any of the n! possible preference lists to each man and woman uniformly at random. Lemma 9. The probability of the number of maximum size chains of disjoint stable matchings exceeding ( n ln n ) ln n is at most O( (ln n) 2 n 2 ). Proof. Let S be the random variable denoting the number of stable matchings in a random stable matching instance. Pittel [16] showed that E[S] = Θ(n ln n). Thus, there exist non-negative reals m 1 , m 2 such that m 1 n ln n ≤ E[S] ≤ m 2 n ln n for sufficiently large n. Further, Lennon and Pittel [11] established that V ar(S) = σ 2 = O((n ln n) 2 ). Thus, for sufficiently large n, there exists a non-negative real number c such that V ar(S) ≤ c 2 (n ln n) 2 .
Thus, for a parameter k, we have P r(S ≥ m 1 n ln n + kcn ln n) ≤ P r(S ≥ m 1 n ln n + kcn ln n ∪ S ≤ m 2 n ln n − kcn ln n) where the last inequality follows from Chebyshev's inequality. Thus, if f (k) = m 1 n ln n + kcn ln n, then P r(S ≥ f (k)) ≤ 1 k 2 . Let L 0 , L 1 , . . . , L t−1 be the sub-lattices constructed in Algorithm 3 where t − 1 = k. Let S i = |L i | for 0 ≤ i ≤ k. Let p = |P |, the number of maximumlength chains of disjoint stable matchings in the given instance. From Lemma ??, Si t ) t , where the last inequality follows from the AM-GM inequality. Since k i=0 S i ≤ S, p ≤ ( S t ) t . From the above discussions, P r(p ≥ ( n ln n ) ln n ) ≤ P r(( S t ) t ≥ ( n ln n ) ln n ) ≤ P r(S ≥ n 2 ) + P r(t ≥ ln n).
Observe that there exists a positive real m such that f ( n m ln n ) ≤ n 2 . Thus, P r(S ≥ n 2 ) ≤ P r(S ≥ f ( n m ln n )) ≤ m 2 (ln n) 2 n 2 . [Knuth et al 90] establishes that the probability of some person having more than ln n stable partners is superpolynomially small. Clearly, no one can have less than t stable partners since each person features alongide a distinct partner in each matching in a maximum size chain of disjoint stable matchings. Hence, P r(t ≥ ln n) is also super-polynomially small.
Thus, P r(p ≥ ( n ln n ) ln n ) ≤ Proof. As established in the previous lemma (notation carrying over from the proof of the previou lemma), P r(S ≥ n 2 ) ≤ O( (ln n) 2 n 2 ) and P r(p ≥ ( n ln n ) ln n ) ≤ O( (ln n) 2 n 2 ) and hence, a simple union bound returns P r(S ≥ n 2 ∪p ≥ ( n ln n ) ln n ) ≤ O( (ln n) 2 n 2 ).

Conclusion
We consider the classical Stable Matching problem and address the question of finding a largest pairwise disjoint collection of solutions to this problem. We show that such a collection can in fact be found in time linear in the input size. The collection of stable matchings that our algorithm finds has the additional property that they form a chain in the distributive lattice of stable matchings. To the best of our knowledge this is the first work on finding pairwise disjoint stable matchings, though this question has received much attention for bipartite matchings without preferences.
A natural next question is what happens when we allow small intersections between the stable matchings. In particular: is the problem of finding a collection of k stable matchings such that no two of them share more than one edge, solvable in polynomial time? Or is this already NP-hard? Another interesting problem is whether we can find a largest edge-disjoint collection of stable matchings for the related Stable Roommates problem, in polynomial time.