Changes
solved
Can we decide in polynomial time if a [[Stable matching#Preference system|preference system]] (without ties) has a [[Stable matching#Popular matching|popular matching]]?
</onlyinclude>
[[File:solved_b.jpg]]
It was shown by {{ColourA|Gupta, Misra, Saurabh, and Zehavi}} <ref name="Gu"/> and independently by {{ColourA|Faenza, Kavitha, Powers, and Zhang}} <ref name="FaKa"/> that the problem is NP-complete. This result was further strengthened by Cseh and Kavitha <ref name="CsKa"/> who showed that the problem remains hard in complete graphs, i.e. non-bipartite preference systems with complete lists.
==Remarks==
<ref name="HuKa3">C.-C. Huang, T. Kavitha, ''Popularity, Mixed Matchings, and Self-duality'', SODA 2017, [http://dx.doi.org/10.1137/1.9781611974782.151 DOI link]</ref>
<ref name="Gu">S. Gupta, P. Misra, S. Saurabh, and M. Zehavi, ''Popular Matching in Roommates Setting is NP-hard'' (2018),
SODA 2019, [https://doi.org/10.1137/1.9781611975482.174 DOI link], [https://arxiv.org/abs/1803.09370 arXiv link]</ref>
<ref name="FaKa">Y. Faenza, T. Kavitha, V. Powers, and X. Zhang, ''Popular Matchings and Limits to Tractability'' (2018),
SODA 2019, [https://doi.org/10.1137/1.9781611975482.173 DOI link], [https://arxiv.org/abs/1805.11473 arXiv link]</ref>
<ref name="CsKa">Á. Cseh, T. Kavitha, ''Popular Matchings in Complete Graphs'' (2018), [https://arxiv.org/abs/1807.01112 arXiv link]</ref>
<references/>
[[Category:Stable matchings and kernels]]
[[Category:Open Solved Problems]]
