Optimal popular matchings

In this paper we consider the problem of computing an “optimal” popular matching. We assume that our input instance G=(A∪P,E1∪̇⋯∪̇Er) admits a popular matching and here we are asked to return not any popular matching but an optimal popular matching, where the definition of optimality is given as a part of the problem statement; for instance, optimality could be fairness in which case we are required to return a fair   popular matching. We show an O(n2+m)O(n2+m) algorithm for this problem, assuming that the preference lists are strict, where mm is the number of edges in GG and nn is the number of applicants.