Article ID: | iaor20104952 |
Volume: | 58 |
Issue: | 1 |
Start Page Number: | 170 |
End Page Number: | 187 |
Publication Date: | Sep 2010 |
Journal: | Algorithmica |
Authors: | Marx Dniel, Schlotter Ildik |
Keywords: | graphs |
We consider the variant of the classical Stable Marriage problem where preference lists can be incomplete and may contain ties. In such a setting, finding a stable matching of maximum size is NP-hard. We study the parameterized complexity of this problem, where the parameter can be the number of ties, the maximum or the overall length of ties. We also investigate the applicability of a local search algorithm for the problem. Finally, we examine the possibilities for giving an FPT algorithm or an FPT approximation algorithm for finding an egalitarian or a minimum regret matching.