Disjoint Stable Matchings in Linear Time

Autor:	Ganesh, Aadityan, HV, Vishwa Prakash, Nimbhorkar, Prajakta, Philip, Geevarghese
Rok vydání:	2020
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Computer Science and Game Theory
Druh dokumentu:	Working Paper
Popis:	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. Comment: Conference: International Workshop on Graph-Theoretic Concepts in Computer Science 2021 (https://wg2021.mimuw.edu.pl)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2011.13248 Zobrazit plný text záznamu View this record from Arxiv