X
Classified Rank-Maximal Matchings and Popular Matchings – Algorithms and Hardness
Published in Springer Verlag
2019
Volume: 11789 LNCS

Pages: 244 - 257
Abstract
In this paper, we consider the problem of computing an optimal matching in a bipartite graph $$G=(A\cup P, E)$$ where elements of A specify preferences over their neighbors in P, possibly involving ties, and each vertex can have capacities and classifications. A classification $$\mathcal {C}_u$$ for a vertex u is a collection of subsets of neighbors of u. Each subset (class) $$C\in \mathcal {C}_u$$ has an upper quota denoting the maximum number of vertices from C that can be matched to u. The goal is to find a matching that is optimal amongst all the feasible matchings, which are matchings that respect quotas of all the vertices and classes. We consider two well-studied notions of optimality namely popularity and rank-maximality. The notion of rank-maximality involves finding a matching in G with maximum number of rank-1 edges, subject to that, maximum number of rank-2 edges and so on. We present an $$O(|E|^2)$$ -time algorithm for finding a feasible rank-maximal matching, when each classification is a laminar family. We complement this with an NP-hardness result when classes are non-laminar even under strict preference lists, and even when only posts have classifications, and each applicant has a quota of one. We show an analogous dichotomy result for computing a popular matching amongst feasible matchings (if one exists) in a bipartite graph with posts having capacities and classifications and applicants having a quota of one. To solve the classified rank-maximal and popular matchings problems, we present a framework that involves computing max-flows iteratively in multiple flow networks. Besides giving polynomial-time algorithms for classified rank-maximal and popular matching problems, our framework unifies several algorithms from literature [1, 10, 12, 15]. © Springer Nature Switzerland AG 2019.
Journal Data powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Data powered by TypesetSpringer Verlag 03029743 No
Concepts (13)
• C (programming language)
• Hardness
• Iterative methods
• Polynomial approximation
• Bipartite graphs
• MATCHINGS
• MAXIMALITY
• NP-HARDNESS RESULTS
• Polynomial-time algorithms
• POPULAR MATCHING PROBLEMS
• POPULARITY
• RANK-MAXIMAL MATCHING
• Graph theory