Computing at Glasgow University
Paper ID: 9011
DCS Tech Report Number: TR-2008-292

Popular Matchings: Structure and Algorithms
McDermid,E. Irving,R.W.

Publication Type: Tech Report (internal)
Appeared in: DCS Technical Report Series
Page Numbers : 1-20
Publisher: Dept of Computing Science, University of Glasgow
Year: 2008

An instance of the popular matching problem (POP-M) consists of a set of applicants and a set of posts. Each applicant has a preference list that strictly ranks a subset of the posts. A matching M of applicants to posts is popular if there is no other matching M' such that more applicants prefer M' to M than prefer M to M'. Abraham et al described a linear time algorithm to determine whether a popular matching exists for a given instance of POP-M, and if so to find a largest such matching. A number of variants and extensions of POP-M have recently been studied. This paper provides a characterization of the set of popular matchings for an arbitrary POP-M instance in terms of a structure called the switching graph, a directed graph computable in linear time from the preference lists. We show that the switching graph can be exploited to yield efficient algorithms for a range of associated problems, including the counting and enumeration of the set of popular matchings, generation of a popular matching uniformly at random, finding all applicant-post pairs that can occur in a popular matching, and computing popular matchings that satisfy various additional optimality criteria. Our algorithms for computing such optimal popular matchings improve those described in a recent paper by Kavitha and Nasre.

Keywords: Matching, Graphs, Optimal solutions, Enumeration

PDF Bibtex entry Endnote XML