Deciding the existence of popular matchings

From Egres Open
Jump to: navigation, search

Can we decide in polynomial time if a preference system (without ties) has a popular matching?


If there are no ties, then every stable matching is popular, so the question is trivial for bipartite preference systems without ties. In this case a largest popular matching can also be found efficiently [1]. If ties are allowed, then the bipartite case is NP-complete by a result of Biró, Irving and Manlove [2], but solvable in polynomial time if only one of the two classes have preferences [3].

In the non-bipartite case, Biró et al. [2] gave a fast algorithm to decide if a matching is popular or not. Huang and Kavitha [4] introduced the notion of unpopularity factor, and showed that it is NP-hard to find a matching with the least unpopularity factor. In another paper [5], they showed that it is NP-hard to find a maximum-weight popular matching, while a maximum-weight popular half-integral matching can be found in polynomial time.

See also

himwiki:Popular matchings in non-bipartite graphs

Finding the largest popular matching in a bipartite graph


  1. C.-C. Huang, T. Kavitha, Popular Matchings in the Stable Marriage Problem, DOI link, author link
  2. 2.0 2.1 P. Biró, R.W. Irving, D.F. Manlove, Popular matchings in the Marriage and Roommates problems, Technical Report
  3. D. J. Abraham, R. W. Irving, T. Kavitha, K. Mehlhorn. Popular matchings, SIAM Journal on Computing 37 (2007), 1030-1045. DOI link, author link
  4. C.-C. Huang, T. Kavitha, Near-Popular Matchings in the Roommates Problem, DOI link, author link
  5. C.-C. Huang, T. Kavitha, Popularity, Mixed Matchings, and Self-duality, SODA 2017, DOI link