Testing popularity in linear time via maximum matching

Bérczi-Kovács, Erika and Kosztolányi, Kata (2025) Testing popularity in linear time via maximum matching. DISCRETE APPLIED MATHEMATICS, 366. pp. 152-160. ISSN 0166-218X

Preview

Text 2312.01880v3.pdf - Draft Version Available under License Creative Commons Attribution. Download (195kB) | Preview

Abstract

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 struc- tured dual witness than previous ones. Based on this result we give a combinatorial charac- terization of fractional popular matchings, which is a special class of popular matchings.

Actions (login required)

Edit Item