Disjoint stable matchings in linear time
Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG …, 2021•Springer
We show that given a Stable Matching instance GG as input, we can find a largest collection
of pairwise edge-disjoint stable matchings of GG 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 GG 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önig's …
of pairwise edge-disjoint stable matchings of GG 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 GG 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önig's …
Abstract
We show that given a Stable Matching instance as input, we can find a largest collection of pairwise edge-disjoint stable matchings of 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 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önig’s characterization with Tutte’s -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.
Springer