Abstract
An instance of the super-stable matching problem with incomplete lists and ties is an undirected bipartite graph \(G = (A \cup B, E)\), with an adjacency list being a linearly ordered list of ties. Ties are subsets of vertices equally good for a given vertex. An edge \((x,y) \in E \backslash M\) is a blocking edge for a matching M if by getting matched to each other neither of the vertices x and y would become worse off. Thus, there is no disadvantage if the two vertices would like to match up. A matching M is super-stable if there is no blocking edge with respect to M. It has previously been shown that super-stable matchings form a distributive lattice [14, 23] and the number of super-stable matchings can be exponential in the number of vertices. We give two compact representations of size O(m) that can be used to construct all super-stable matchings, where m denotes the number of edges in the graph. The construction of the second representation takes O(mn) time, where n denotes the number of vertices in the graph, and gives an explicit rotation poset similar to the rotation poset in the classical stable marriage problem. We also give a polyhedral characterization of the set of all super-stable matchings and prove that the super-stable matching polytope is integral, thus solving an open problem stated in the book by Gusfield and Irving [4].
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
Birkhoff, G., et al.: Rings of sets. Duke Math. J. 3(3), 443–454 (1937)
Dean, B., Jalasutram, R.: Factor revealing lps and stable matching with ties and incomplete lists. In: Proceedings of the 3rd International Workshop on Matching Under Preferences, pp. 42–53 (2015)
Fleiner, T., Irving, R.W., Manlove, D.F.: Efficient algorithms for generalized stable marriage and roommates problems. Theoret. Comput. Sci. 381(1–3), 162–176 (2007)
Gusfield, D., Irving, R.W.: The Stable marriage problem - structure and algorithms. Foundations of computing series. MIT Press (1989)
Huang, C.-C., Kavitha, T.: An improved approximation algorithm for the stable marriage problem with one-sided ties. In: Lee, J., Vygen, J. (eds.) IPCO 2014. LNCS, vol. 8494, pp. 297–308. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07557-0_25
Irving, R.W.: Stable marriage and indifference. Discret. Appl. Math. 48(3), 261–272 (1994)
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
Iwama, K., Miyazaki, S., Yanagisawa, H.: A 25/17-approximation algorithm for the stable marriage problem with one-sided ties. Algorithmica 68(3), 758–775 (2014). https://doi.org/10.1007/s00453-012-9699-2
Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.E.: Strongly stable matchings in time o (nm) and extension to the hospitals-residents problem. ACM Trans. Algorithms (TALG) 3(2), 15-es (2007)
Király, Z.: Linear time local approximation algorithm for maximum stable marriage. Algorithms 6(3), 471–484 (2013)
Kunysz, A.: An algorithm for the maximum weight strongly stable matching problem. In: 29th International Symposium on Algorithms and Computation (ISAAC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
Kunysz, A., Paluch, K., Ghosal, P.: Characterisation of strongly stable matchings. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 107–119. SIAM (2016)
Lam, C.K., Plaxton, C.G.: A (1+ 1/e)-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2823–2840. SIAM (2019)
Manlove, D.F.: The structure of stable marriage with indifference. Discret. Appl. Math. 122(1–3), 167–181 (2002)
Marchetti-Spaccamela, A., Nanni, U., Rohnert, H.: Maintaining a topological order under edge insertions. Inf. Process. Lett. 59(1), 53–58 (1996)
McDermid, E.: A 3/2-approximation algorithm for general stable marriage. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 689–700. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02927-1_57
Paluch, K.: Faster and simpler approximation of stable matchings. Algorithms 7(2), 189–202 (2014)
Pearce, D.J., Kelly, P.H.: Online algorithms for topological order and strongly connected components. Technical report, Citeseer (2003)
Pearce, D.J.: Some directed graph algorithms and their application to pointer analysis. Ph.D. thesis, University of London (2005)
Radnai, A.: Approximation algorithms for the stable matching problem. Eötvös Lorand University (2014)
Rothblum, U.G.: Characterization of stable matchings as extreme points of a polytope. Math. Program. 54(1–3), 57–67 (1992)
Scott, S.: A study of stable marriage problems with ties. Ph.D. thesis. University of Glasgow (2005)
Spieker, B.: The set of super-stable marriages forms a distributive lattice. Discret. Appl. Math. 58(1), 79–84 (1995)
Teo, C.P., Sethuraman, J.: The geometry of fractional stable matchings and its applications. Math. Oper. Res. 23(4), 874–891 (1998)
Vate, J.H.V.: Linear programming brings marital bliss. Oper. Res. Lett. 8(3), 147–153 (1989)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Hu, C., Garg, V.K. (2021). Characterization of Super-Stable Matchings. In: Lubiw, A., Salavatipour, M., He, M. (eds) Algorithms and Data Structures. WADS 2021. Lecture Notes in Computer Science(), vol 12808. Springer, Cham. https://doi.org/10.1007/978-3-030-83508-8_35
Download citation
DOI: https://doi.org/10.1007/978-3-030-83508-8_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-83507-1
Online ISBN: 978-3-030-83508-8
eBook Packages: Computer ScienceComputer Science (R0)