The inverse popular matching problem asks for the minimum total cost of changing graph vertex preference lists to make a prescribed
matching popular. The input is a finite
graph 
, strict preferences at each graph
vertex over its neighbors, a fixed matching 
, and a positive integer
cost 
for changing the preferences of graph vertex 
. Being unmatched is ranked below every neighbor. A
chosen set 
is feasible if some changes to preferences at its vertices,
leaving all other preferences fixed, make 
a popular matching. Its
cost is 
(Bérczi-Kovács and Szabó 2026, p. 3).
The problem is NP-hard even when the prescribed matching is perfect
and every cost is 1. It is also NP-hard on bipartite graphs with every cost equal to 1 and maximum
vertex degree at most 7. If the graph
is bipartite and 
is a maximum matching,
however, the minimum cost can be determined in polynomial
time. Bérczi-Kovács and Szabó (2026) also give a min-max
characterization for this case.
