The inverse popular matching problem asks for the minimum total cost of changing vertex preference lists to make a prescribed matching
popular. The input is a graph 
, strict preferences at each graph
vertex over its neighbors, a fixed matching 
,
and a positive 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).
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.
