Finding the largest popular matching in a bipartite graph

From Egres Open
Jump to: navigation, search

Can we find in polynomial time a largest popular matching in a bipartite preference system (without ties)?

Solved c.jpg

Chien-Chung Huang and Telikepalli Kavitha [1] gave a polynomial algorithm for the problem. A linear time algorithm is presented in [2]. Cseh and Kavitha [3] gave a linear time algorithm for deciding if a given edge is in a popular matching.


The question was first asked by Gärdenfors [4]. Abraham et al.[5] solved the problem in the case when only one of the two classes have preferences (the house allocation problem). They can decide if there is a popular matching and find a largest popular matching even if the preference lists have ties. Mestre [6] and Sng and Manlove [7] extended this result (in case of no ties) to the node-weighted popular matching problem. The complexity of both the node-weighted and edge-weighted problem is open if both sides have strict preferences.

Biró, Irving and Manlove [8] showed that if we allow ties in a bipartite preference system, then it is NP-complete to decide if a popular matching exists.

In the non-bipartite case, Biró et al. [8] gave a fast algorithm to decide if a matching is popular or not. Huang and Kavitha [9] introduced the notion of unpopularity factor, and showed that it is NP-hard to find a matching with the least unpopularity factor. It is open if the existence of a popular matching can be decided in polynomial time, see the problem Deciding the existence of popular matchings.


  1. C.-C. Huang, T. Kavitha, Popular Matchings in the Stable Marriage Problem, DOI link, author link
  2. T. Kavitha, Popularity vs maximum cardinality in the stable marriage setting, DOI link, Citeseer link
  3. Á. Cseh, T. Kavitha, Popular edges and dominant matchings, DOI link, arXiv link
  4. P. Gärdenfors, Match making: Assignments based on bilateral preferences, Behavioural Science 20 (1975), 166-173. DOI link
  5. D. J. Abraham, R. W. Irving, T. Kavitha, K. Mehlhorn. Popular matchings, SIAM Journal on Computing 37 (2007), 1030-1045. DOI link, author link
  6. J. Mestre, Weighted Popular Matchings, Lecture Notes in Computer Science 4051 (2006), 715-726. DOI link. arXiv link
  7. C. T. S. Sng, D. F. Manlove, Popular matchings in the weighted capacitated house allocation problem, Journal of Discrete Algorithms. DOI link
  8. 8.0 8.1 P. Biró, R.W. Irving, D.F. Manlove, Popular matchings in the Marriage and Roommates problems, Technical Report
  9. C.-C. Huang, T. Kavitha, Near-Popular Matchings in the Roommates Problem, DOI link, author link