Adil, Deeksha ; Gupta, Sushmita ; Roy, Sanjukta ; Saurabh, Saket ; Zehavi, Meirav (2018) Parameterized algorithms for stable matching with ties and incomplete lists Theoretical Computer Science, 723 . pp. 1-10. ISSN 0304-3975
Full text not available from this repository.
Official URL: http://doi.org/10.1016/j.tcs.2018.03.015
Related URL: http://dx.doi.org/10.1016/j.tcs.2018.03.015
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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 123394 |
| Deposited On: | 16 Sep 2021 05:48 |
| Last Modified: | 16 Sep 2021 05:48 |
Repository Staff Only: item control page
