Deciding the existence of popular matchings
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 . If ties are allowed, then the bipartite case is NP-complete by a result of Biró, Irving and Manlove , but solvable in polynomial time if only one of the two classes have preferences .
In the non-bipartite case, Biró et al.  gave a fast algorithm to decide if a matching is popular or not. Huang and Kavitha  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 , 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.
- C.-C. Huang, T. Kavitha, Popular Matchings in the Stable Marriage Problem, DOI link, author link
- P. Biró, R.W. Irving, D.F. Manlove, Popular matchings in the Marriage and Roommates problems, Technical Report
- D. J. Abraham, R. W. Irving, T. Kavitha, K. Mehlhorn. Popular matchings, SIAM Journal on Computing 37 (2007), 1030-1045. DOI link, author link
- C.-C. Huang, T. Kavitha, Near-Popular Matchings in the Roommates Problem, DOI link, author link
- C.-C. Huang, T. Kavitha, Popularity, Mixed Matchings, and Self-duality, SODA 2017, DOI link