Finding the largest popular matching in a bipartite graph
Chien-Chung Huang and Telikepalli Kavitha  gave a polynomial algorithm for the problem. A linear time algorithm is presented in . Cseh and Kavitha  gave a linear time algorithm for deciding if a given edge is in a popular matching.
The question was first asked by Gärdenfors . Abraham et al. 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  and Sng and Manlove  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  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.  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. 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.
- C.-C. Huang, T. Kavitha, Popular Matchings in the Stable Marriage Problem, DOI link, author link
- T. Kavitha, Popularity vs maximum cardinality in the stable marriage setting, DOI link, Citeseer link
- Á. Cseh, T. Kavitha, Popular edges and dominant matchings, DOI link, arXiv link
- P. Gärdenfors, Match making: Assignments based on bilateral preferences, Behavioural Science 20 (1975), 166-173. DOI link
- D. J. Abraham, R. W. Irving, T. Kavitha, K. Mehlhorn. Popular matchings, SIAM Journal on Computing 37 (2007), 1030-1045. DOI link, author link
- J. Mestre, Weighted Popular Matchings, Lecture Notes in Computer Science 4051 (2006), 715-726. DOI link. arXiv link
- C. T. S. Sng, D. F. Manlove, Popular matchings in the weighted capacitated house allocation problem, Journal of Discrete Algorithms. DOI link
- P. Biró, R.W. Irving, D.F. Manlove, Popular matchings in the Marriage and Roommates problems, Technical Report
- C.-C. Huang, T. Kavitha, Near-Popular Matchings in the Roommates Problem, DOI link, author link