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?

Solved b.jpg

It was shown by Gupta, Misra, Saurabh, and Zehavi [1] and independently by Faenza, Kavitha, Powers, and Zhang [2] that the problem is NP-complete. This result was further strengthened by Cseh and Kavitha [3] who showed that the problem remains hard in complete graphs, i.e. non-bipartite preference systems with complete lists.

Remarks

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 [4]. If ties are allowed, then the bipartite case is NP-complete by a result of Biró, Irving and Manlove [5], but solvable in polynomial time if only one of the two classes have preferences [6].

In the non-bipartite case, Biró et al. [5] gave a fast algorithm to decide if a matching is popular or not. Huang and Kavitha [7] 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 [8], 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

References

  1. ↑ S. Gupta, P. Misra, S. Saurabh, and M. Zehavi, Popular Matching in Roommates Setting is NP-hard (2018), SODA 2019, DOI link, arXiv link
  2. ↑ Y. Faenza, T. Kavitha, V. Powers, and X. Zhang, Popular Matchings and Limits to Tractability (2018), SODA 2019, DOI link, arXiv link
  3. ↑ Á. Cseh, T. Kavitha, Popular Matchings in Complete Graphs (2018), arXiv link
  4. ↑ C.-C. Huang, T. Kavitha, Popular Matchings in the Stable Marriage Problem, DOI link, author link
  5. ↑ 5.0 5.1 P. Biró, R.W. Irving, D.F. Manlove, Popular matchings in the Marriage and Roommates problems, Technical Report
  6. ↑ D. J. Abraham, R. W. Irving, T. Kavitha, K. Mehlhorn. Popular matchings, SIAM Journal on Computing 37 (2007), 1030-1045. DOI link, author link
  7. ↑ C.-C. Huang, T. Kavitha, Near-Popular Matchings in the Roommates Problem, DOI link, author link
  8. ↑ C.-C. Huang, T. Kavitha, Popularity, Mixed Matchings, and Self-duality, SODA 2017, DOI link
Retrieved from "http://lemon.cs.elte.hu/egres/internals/index.php5?title=Deciding_the_existence_of_popular_matchings&oldid=2443"