# Popular matchings in non-bipartite graphs

(suggested by Ágnes Cseh)

# Problem Statement

Let be a not necessarily bipartite graph. Each vertex has a strict preference list ranking its neighbors in an order of preference. A matching is *popular* if there is no matching such that the number of vertices that prefer to is more than the number that prefer to .

**Is there a popular matching in ?**

# What is known?

The problem is well studied for the **bipartite case**. There, popular matchings always exist, moreover, every stable matching is popular and in fact, these form a subclass of minimum size popular matchings. One can efficiently compute maximum size popular matchins as well. On the other hand, if ties are permitted in the preferences, it is NP-hard to determine whether a popular matching exists.

For the **general case**, it is known that checking whether a given matching is popular can be done in polynomial time. It carries over from the bipartite case that stable matchings are popular. One can decide efficiently whether an instance admits a stable matching simply by investigating the occurence of *odd parties* (odd preference cycles). However, instances with no stable matchings can admit popular matchings. The approximation concept of *unpopularity factor* has also been studied. The unpopularity factor of measures by what factor any matching can be more popular than . It is known that always admits a matching whose unpopularity factor is and such a matching can be computed in linear time. Computing a least unpopularity factor matching is NP-hard. In fact, for any , it is NP-hard to compute a matching whose unpopularity factor is at most of the optimal.

# Challenge

Determine the complexity of the popular matching problem in general graphs.