# Finding all stable matchings in stable marriage problem

I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm does). The only solution I have is to recursively enumerate all the possible matchings, discarding the recursive branches which do not satisfy the conditions. This algorithm has a complexity of O(n!), with n being the number of items in each set.

I found this similar question that shows that the upper bound to the number of solutions is exponential. Is there any better algorithm than the one I have so far?

In the context of similar questions, this paper by Gusfield comes up. However, it solves a different problem.

• Here is some idea that should at least prune the search by some chunk (probably not asymptotically): Compute the man-optimal stable matching with GS and the woman-optimal stable matching with GS with roles of men and women reversed. These two matchings give you the top and bottom element of the lattice of all stable matchings. If it's the same, you are already done, otherwise, restrict your search on this lattice by using only the lattice operations. Nov 2, 2023 at 12:46
• Because there can be exponentially many solutions, any such algorithm will have to take exponential time in the worst case. Are you sure you want to know all solutions? Is it possible you have an XY problem?
– D.W.
Nov 2, 2023 at 18:32
• @ttnick I have looked into the lattice of all stable matchings. It seems to me that you can't use lattice operations to explore the lattice starting from the top and bottom elements, since applying the operations to these two elements always returns one of the two. Am I perhaps missing something?
– void
Nov 2, 2023 at 18:55
• @D.W. Yes, I need all the solutions: it's the starting point of an assignment. We'll have to expand the problem further, but first we need an algorithm to obtain all the solutions.
– void
Nov 2, 2023 at 18:56
• @void, sorry that was not phrased too well: Giving top and bottom matching this gives you for every man $m$ with preference list $[w_{m1}, w_{m2}, \ldots, w_{mn}]$ the sublist $[w_{mk}, \ldots, w_{m\ell}]$ of women for which there exists a stable matching containing $\{m, w_{mj}\}$. In that sense, it restricts your search space. If you have managed to find more matchings, you will also be able to find even more by applying join and meet. Nov 3, 2023 at 15:06