Answers are grounded in this paper and cite their sources.
Our input is a complete graph G on n vertices where each vertex has a strict ranking of all other vertices in G . The goal is to construct a matching in G that is popular . A matching M is popular if M does not lose a head-to-head election against any matching $$M'$$ M ′ : here each vertex casts a vote for the matching in ,M'\ { M , M ′ } in which it gets a better assignment. Popular matchings need not exist in the given instance G and the popular matching problem is to decide whether one exists or not. The popular matching problem in G is easy to solve for odd n . Surprisingly, the problem becomes NP NP -complete for even n , as we show here. This is one of the few graph theoretic problems efficiently solvable when n has one parity and NP NP -complete when n has the other parity.
No takes yet. Share an insight, caveat, or question.
Cseh et al. (2021) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: