Before revision:  In this setting, our goal is to compute a min-cost stable matching that matches all the agents . We show that the problem is NP-hard even under very severe restrictions on the instance. We complement our negative results by presenting approximation algorithms for general case and a fast exponential algorithm for a special case .
After revision:  In this setting, our goal is to compute a min-cost stable matching that matches all agents and is optimal with respect to the cost criteria. We study two optimization problems with respect to the costs and show that there is a sharp contrast in the complexity status of the two optimization criteria. We also establish the connection of our model with the stable extension problem in an apparently different two-round setting of the stable matching problem. We show that our results in the SMFQ setting generalize the stable extension problem .