Paper Info
Title
Classified Rank-Maximal Matchings And Popular Matchings - Algorithms And Hardness
Abstract
In this paper, we consider the problem of computing an optimal matching in a bipartite graph G = (A boolean OR 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 C-u for a vertex u is a collection of subsets of neighbors of u. Each subset (class) C is an element of 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(vertical bar E vertical bar(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].
Year
DOI
Venue
2019
10.1007/978-3-030-30786-8_19
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2019)
Keywords
Field
DocType
Bipartite graphs, Popularity, Rank-maximality, Matchings under classifications
Discrete mathematics,Combinatorics,Optimal matching,Vertex (geometry),Computer science,Bipartite graph
Conference
Volume
ISSN
Citations 
11789
0302-9743
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Meghana Nasre19812.80
Prajakta Nimbhorkar217015.04
Nada Pulath300.34