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.

Remarks

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.

References

  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
Retrieved from "http://lemon.cs.elte.hu/egres/internals/index.php5?title=Finding_the_largest_popular_matching_in_a_bipartite_graph&oldid=2427"