Parameterized algorithms for stable matching with ties and incomplete lists

Please use this identifier to cite or link to this item: http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/3843

Title:	Parameterized algorithms for stable matching with ties and incomplete lists
Authors:	ADIL, DEEKSHA Gupta, Sushmita Roy, Sanjukta Saurabh, Saket Zehavi, Meirav Dept. of Mathematics
Keywords:	Parameterized algorithms Parameterized Complexity Preference list 2018
Issue Date:	May-2018
Publisher:	Elsevier B.V.
Citation:	Theoretical Computer Science, 723, 1-10.
Abstract:	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.
URI:	http://dr.iiserpune.ac.in:8080/xmlui/handle/123456789/3843 https://doi.org/10.1016/j.tcs.2018.03.015
ISSN:	0304-3975
Appears in Collections:	JOURNAL ARTICLES

Files in This Item:

There are no files associated with this item.