Please use this identifier to cite or link to this item: http://hdl.handle.net/10419/222073
Authors: 
Cseh, Ágnes
Kavitha, Telikepalli
Year of Publication: 
2020
Series/Report no.: 
CERS-IE Working Papers No. CERS-IE WP - 2020/4
Abstract: 
Our input is a complete graph G on n vertices where each vertex has a strictranking of all other vertices in G. The goal is to construct a matching in G that is "globallystable" or popular. A matching M is popular if M does not lose a head-to-head election againstany matching M': here each vertex casts a vote forthe matching in {M,M'} in which it gets abetter assignment. Popular matchings need not exist in the given instance G and the popularmatching problem is to decide whether one exists or not. The popular matching problem in Gis easy to solve for odd n. Surprisingly, the problem becomes NP-hard for even n, as we showhere. This seems to be the first graph theoretic problem that is efficiently solvable when n hasone parity and NP-hard when n has the other parity.
Subjects: 
popular matching
NP-completeness
polynomial algorithm
stable matching
JEL: 
C63
C78
Document Type: 
Working Paper

Files in This Item:
File
Size
599.04 kB





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.