2

Every Stable Marriage problem has at least one solution. However, how to know the largest number of solutions to a stable marriage problem? The Gale-Shapley algorithm can only find one man-optimal solution. If we use woman-optimal method to run Gale-Shapley, there may be another solution. Are there at most two solutions to an instance of stable marriage, or can Gale-Shapley only find two solutions, and there are some other solutions beyond them?

cela
  • 2,352
  • 3
  • 21
  • 43
microbit
  • 319
  • 3
  • 10
  • There definitely can be more than two solutions. The [wikipedia article](http://en.wikipedia.org/wiki/Stable_marriage_problem) gives an example with three solutions. – Don Roby Sep 02 '14 at 22:17
  • 1
    I would be more than a little surprised if this weren't a #P-complete problem. – David Eisenstat Sep 02 '14 at 22:26
  • 1
    @DavidEisenstat Your suspicion is correct: [The Complexity of Counting Stable Marriages](http://epubs.siam.org/doi/abs/10.1137/0215048), SIAM J. Comput., 15(3), 655–667 – mhum Sep 02 '14 at 22:48
  • 3
    This question appears to be off-topic because it is about Computer Science (which has its own site), not programming. – MSalters Sep 02 '14 at 23:50

1 Answers1

2

See https://cstheory.stackexchange.com/questions/5619/what-is-the-maximum-number-of-stable-marriages-for-an-instance-of-the-stable-mar where it is discussed that an exponential worst-case lower bound of Omega(2.28^n) stable marriages is given for all n for n men/women (by giving a family of examples where this many stable marriages are possible).

Community
  • 1
  • 1
user2566092
  • 4,631
  • 15
  • 20