  Popularity is an approach in mechanism design to find fair structures in a
graph, based on the votes of the nodes. Popular matchings are the relaxation of
stable matchings: given a graph G=(V,E) with strict preferences on the
neighbors of the nodes, a matching M is popular if there is no other matching
M' such that the number of nodes preferring M' is more than those preferring M.
This paper considers the popularity testing problem, when the task is to decide
whether a given matching is popular or not. Previous algorithms applied
reductions to maximum weight matchings. We give a new algorithm for testing
popularity by reducing the problem to maximum matching testing, thus attaining
a linear running time O(|E|).
  Linear programming-based characterization of popularity is often applied for
proving the popularity of a certain matching. As a consequence of our algorithm
we derive a more structured dual witness than previous ones. Based on this
result we give a combinatorial characterization of fractional popular
matchings, which are a special class of popular matchings.
