Parameterized algorithms for stable matching with ties and incomplete lists

摘要

We study the parameterized complexity of NP-hard optimization versions of STABLE MATCHING and STABLE ROOMMATES in the presence of ties and incomplete lists. These problems model many real-life situations where solutions have to satisfy certain predefined criterion of suitability and compatibility. Specifically, our objective is to maximize/minimize the size of the stable matching. Our main theorems state that STABLE MATCHING and STABLE ROOMMATES admit small kernels. Consequently, we also conclude that STABLE MATCHING is fixed-parameter tractable (FPT) with respect to solution size, and that STABLE ROOMMATES is FPT with respect to a structural parameter. Finally, we analyze the special case where the input graph is planar. (C) 2018 Elsevier B.V. All rights reserved.