Preference swaps for the stable matching problem. (English) Zbl 07676483
Summary: An instance \(I\) of the Stable Matching Problem (SMP) is given by a bipartite graph with a preference list of neighbors for every vertex. A swap in \(I\) is the exchange of two consecutive vertices in a preference list. A swap can be viewed as a smallest perturbation of \(I\). Boehmer et al. (2021) designed a polynomial-time algorithm for finding the minimum number of swaps required to turn a given maximal matching into a stable matching. We generalize this result to the many-to-many version of SMP. We do so first by introducing a new representation of SMP as an extended bipartite graph and subsequently by reducing the problem to submodular minimization. It is a natural problem to establish the computational complexity of deciding whether at most \(k\) swaps are enough to turn \(I\) into an instance where one of the maximum matchings is stable. Using a hardness result of Gupta et al. (2020), we prove that this problem is NP-hard and, moreover, this problem parameterised by \(k\) is W[1]-hard. We also obtain a lower bound on the running time for solving the problem using the Exponential Time Hypothesis.
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Balinski, M.; Ratier, G., Of stable marriages and graphs, and strategy and polytopes, SIAM Rev., 39, 4, 575-604 (1997) · Zbl 0890.90188 |
| [2] | Balinski, M.; Ratier, G., Graphs and marriages, Am. Math. Mon., 105, 5, 430-445 (1998) · Zbl 0913.05075 |
| [3] | Boehmer, N.; Bredereck, R.; Heeger, K.; Niedermeier, R., Bribery and control in stable marriage, J. Artif. Intell. Res., 71, 993-1048 (2021) · Zbl 1519.91175 |
| [4] | Bredereck, R.; Chen, J.; Knop, D.; Luo, J.; Niedermeier, R., Adapting stable matchings to evolving preferences, (The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020. The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020 (2020), AAAI Press), 1830-1837 |
| [5] | Chen, J.; Skowron, P.; Sorge, M., Matchings under preferences: strength of stability and trade-offs, ACM Trans. Econ. Comput., 9, 4, 1-55 (2021) |
| [6] | Cygan, M.; Fomin, F. V.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer · Zbl 1334.90001 |
| [7] | Eiben, E.; Knop, D.; Panolan, F.; Suchý, O., Complexity of the Steiner network problem with respect to the number of terminals, (Niedermeier, R.; Paul, C., 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019. 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, Berlin, Germany, March 13-16, 2019. 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019. 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, Berlin, Germany, March 13-16, 2019, LIPIcs, vol. 126 (2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 25:1-25:17 · Zbl 07559134 |
| [8] | Gale, D.; Shapley, L. S., College admissions and the stability of marriage, Am. Math. Mon., 69, 1, 9-15 (1962) · Zbl 0109.24403 |
| [9] | Gupta, S.; Jain, P.; Roy, S.; Saurabh, S.; Zehavi, M., On the (parameterized) complexity of almost stable marriage, (Saxena, N.; Simon, S., 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020. 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, BITS Pilani, K K Birla Goa Campus, Goa, India (Virtual Conference), December 14-18, 2020. 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020. 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, BITS Pilani, K K Birla Goa Campus, Goa, India (Virtual Conference), December 14-18, 2020, LIPIcs, vol. 182 (2020)), 24:1-24:17 |
| [10] | Gutin, G. Z.; Neary, P. R.; Yeo, A., Unique stable matchings (2021), CoRR |
| [11] | Impagliazzo, R.; Paturi, R., Complexity of k-SAT, (Proceedings of the 14th Annual IEEE Conference on Computational Complexity. Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999 (1999), IEEE Computer Society), 237-240 |
| [12] | Kamada, Y.; Kojima, F., Efficient matching under distributional constraints: theory and applications, Am. Econ. Rev., 105, 1, 67-99 (2015) |
| [13] | Maffray, F., Kernels in perfect line-graphs, J. Comb. Theory, Ser. B, 55, 1, 1-8 (1992) · Zbl 0694.05054 |
| [14] | Mai, T.; Vazirani, V. V., Finding stable matchings that are robust to errors in the input, (Azar, Y.; Bast, H.; Herman, G., 26th Annual European Symposium on Algorithms, ESA 2018. 26th Annual European Symposium on Algorithms, ESA 2018, Helsinki, Finland, August 20-22, 2018. 26th Annual European Symposium on Algorithms, ESA 2018. 26th Annual European Symposium on Algorithms, ESA 2018, Helsinki, Finland, August 20-22, 2018, LIPIcs, vol. 112 (2018)), 60:1-60:11 · Zbl 1524.68463 |
| [15] | Mai, T.; Vazirani, V. V., An efficient algorithm for fully robust stable matchings via join semi-sublattices (2020), CoRR |
| [16] | Marx, D., Can you beat treewidth?, Theory Comput., 6, 1, 85-112 (2010) · Zbl 1213.68316 |
| [17] | McVitie, D.; Wilson, L., Stable marriage assignment for unequal sets, BIT Numer. Math., 10, 3, 295-309 (1970) · Zbl 0225.05002 |
| [18] | Roth, A. E., The evolution of the labor market for medical interns and residents: a case study in game theory, J. Polit. Econ., 92, 6, 991-1016 (1984) |
| [19] | Roth, A. E., On the allocation of residents to rural hospitals: a general property of two-sided matching markets, Econometrica, 54, 2, 425-427 (1986) |
| [20] | Schrijver, A., A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Comb. Theory, Ser. B, 80, 2, 346-355 (2000) · Zbl 1052.90067 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
