Improving Man-Optimal Stable Matchings by Minimum Change of Preference Lists

In the stable marriage problem, any instance admits the so-called man-optimal stable matching, in which every man is assigned the best possible partner. However, there are instances for which all men receive low-ranked partners even in the man-optimal stable matching. In this paper we consider the problem of improving the man-optimal stable matching by changing only one man’s preference list. We show that the optimization variant and the decision variant of this problem can be solved in time O( n 3) and O( n 2), respectively, where n is the number of men (women) in an input. We further extend the problem so that we are allowed to change k men’s preference lists. We show that the problem is W[1]-hard with respect to the parameter k and give O( n 2k+1)-time and O( n k+1)-time exact algorithms for the optimization and decision variants, respectively. Finally, we show that the problems become easy when k = n; we give O( n2.5 log n)-time and O( n 2)-time algorithms for the optimization and decision variants, respectively.