Popular matchings in non-bipartite graphs

From himtp
Jump to: navigation, search

(suggested by Ágnes Cseh)

Problem Statement

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

Is there a popular matching in G?


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 M 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 M measures by what factor any matching can be more popular than M. It is known that G always admits a matching whose unpopularity factor is O(log|V|) and such a matching can be computed in linear time. Computing a least unpopularity factor matching is NP-hard. In fact, for any \epsilon > 0, it is NP-hard to compute a matching whose unpopularity factor is at most \frac{4}{3}-\epsilon of the optimal.

Challenge

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

Please add comments here