Abstract
We study several key variants of SMTI - Stable Marriage problem in which the preference lists may contain ties and may be incomplete. A matching is called weakly stable unless there is a man and a woman such that they are currently not matched with each other but if they get matched with each other, then both of them become better off. The COM SMTI problem is to decide whether there exists a complete (in which all men and women are matched) weakly stable matching in an SMTI instance. It is known that the COM SMTI problem is NP-complete. We strengthen this result by proving that this problem remains NP-complete even for the instance SMTI-C, instance where members in each preference list are consecutive with respect to some orderings of the set of men and set of women. On the positive side, we give a polynomial time algorithm for COM SMTI problem for the instance SMTI-STEP, where the preference lists admit step-property, that is, preference list of every man \(m_i\) is the set of all women \(w_j\) such that \(j \le i\) for some ordering of men and some ordering of women. Further, DECIDE_MAX SMTI (resp. DECIDE_MIN SMTI) is the decision version of MAX SMTI (resp. MIN SMTI), the problem of finding a weakly stable matching of maximum (resp. minimum) cardinality in an SMTI instance. Both DECIDE_MAX SMTI and DECIDE_MIN SMTI problems are known to be NP-complete. We improve these results by showing that DECIDE_MAX SMTI and DECIDE_MIN SMTI problems remain NP-complete even for the case where the preference lists admit inclusion ordering and even for the case where the preference lists admit step-property, respectively. Finally, we present a 3/2-approximation algorithm for the MIN SMTI problem with inclusion ordering.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9–15 (1962)
Halldórsson, M.M., et al.: Approximability results for stable marriage problems with ties. Theoret. Comput. Sci. 306(1–3), 431–447 (2003)
Horton, J.D., Kilakos, K.: Minimum edge dominating sets. SIAM J. Discret. Math. 6(3), 375–387 (1993)
Irving, R.W.: Stable marriage and indifference. Discret. Appl. Math. 48(3), 261–272 (1994)
Irving, R.W., Manlove, D.F., O’Malley, G.: Stable marriage with ties and bounded length preference lists. J. Discrete Algorithms 7(2), 213–219 (2009)
Iwama, K., Miyazaki, S., Morita, Y., Manlove, D.: Stable marriage with incomplete lists and ties. In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 443–452. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48523-6_41
Király, Z.: Linear time local approximation algorithm for maximum stable marriage. Algorithms 6(3), 471–484 (2013)
Manlove, D.F., Irving, R.W., Iwama, K., Miyazaki, S., Morita, Y.: Hard variants of stable marriage. Theoret. Comput. Sci. 276(1–2), 261–279 (2002)
Paluch, K.: Faster and simpler approximation of stable matchings. Algorithms 7(2), 189–202 (2014)
Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364–372 (1980)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Panda, B.S., Sachin (2022). Hardness and Approximation Results for Some Variants of Stable Marriage Problem. In: Balachandran, N., Inkulu, R. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2022. Lecture Notes in Computer Science(), vol 13179. Springer, Cham. https://doi.org/10.1007/978-3-030-95018-7_20
Download citation
DOI: https://doi.org/10.1007/978-3-030-95018-7_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-95017-0
Online ISBN: 978-3-030-95018-7
eBook Packages: Computer ScienceComputer Science (R0)