Document Open Access Logo

On the (Parameterized) Complexity of Almost Stable Marriage

Authors Sushmita Gupta, Pallavi Jain, Sanjukta Roy, Saket Saurabh, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.24.pdf
  • Filesize: 0.9 MB
  • 17 pages

Document Identifiers

Author Details

Sushmita Gupta
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Pallavi Jain
  • Indian Institute of Technology Jodhpur, India
Sanjukta Roy
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
  • University of Bergen, Norway
Meirav Zehavi
  • Ben Gurion University of the Negev, Beer Sheva, Israel

Funding

  • Gupta, Sushmita: was supported by SERB-Starting Research Grant (SRG/2019/001870).
  • Saurabh, Saket: Received funding from European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant no. 819416), and Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.
  • Zehavi, Meirav: was supported by ISF grant (no.1176/18) and BSF grant no. 2018302).

Cite AsGet BibTex

Sushmita Gupta, Pallavi Jain, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. On the (Parameterized) Complexity of Almost Stable Marriage. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FSTTCS.2020.24

Abstract

In the Stable Marriage problem, when the preference lists are complete, all agents of the smaller side can be matched. However, this need not be true when preference lists are incomplete. In most real-life situations, where agents participate in the matching market voluntarily and submit their preferences, it is natural to assume that each agent wants to be matched to someone in his/her preference list as opposed to being unmatched. In light of the Rural Hospital Theorem, we have to relax the "no blocking pair" condition for stable matchings in order to match more agents. In this paper, we study the question of matching more agents with fewest possible blocking edges. In particular, the goal is to find a matching whose size exceeds that of a stable matching in the graph by at least t and has at most k blocking edges. We study this question in the realm of parameterized complexity with respect to several natural parameters, k,t,d, where d is the maximum length of a preference list. Unfortunately, the problem remains intractable even for the combined parameter k+t+d. Thus, we extend our study to the local search variant of this problem, in which we search for a matching that not only fulfills each of the above conditions but is "closest", in terms of its symmetric difference to the given stable matching, and obtain an FPT algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Stable Matching
  • Parameterized Complexity
  • Local Search

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. D. J. Abraham, P. Biró, and D. F. Manlove. "Almost stable" matchings in the roommates problem. In International Workshop on Approximation and Online Algorithms (WG), pages 1-14, 2005. Google Scholar
  2. P. Biró, T. Fleiner, R. W. Irving, and D. F. Manlove. The college admissions problem with lower and common quotas. Theoretical Computer Science, 411(34-36):3136-3153, 2010. Google Scholar
  3. P. Biró, D. Manlove, and S. Mittal. Size versus stability in the marriage problem. Theoretical Computer Science, 411(16-18):1828-1841, 2010. Google Scholar
  4. P. Biró, D. F. Manlove, and E. J. McDermid. "Almost stable" matchings in the roommates problem with bounded preference lists. Theoretical Computer Science, 432:10-20, 2012. Google Scholar
  5. J. Chen, D. Hermelin, M. Sorge, and H. Yedidsion. How hard is it to satisfy (almost) all roommates? In International Colloquium on Automata, Languages, and Programming, (ICALP), pages 35:1-35:15, 2018. Google Scholar
  6. J. Chen, P. Skowron, and M. Sorge. Matchings under preferences: Strength of stability and trade-offs. In ACM Conference on Economics and Computation (EC), pages 41-59, 2019. Google Scholar
  7. Á. Cseh and D. F. Manlove. Stable marriage and roommates problems with restricted edges: Complexity and approximability. Discrete Optimization, 20:62-89, 2016. Google Scholar
  8. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  9. R. Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  10. R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  11. M. R. Fellows, F. V. Fomin, D. Lokshtanov, F. A. Rosamond, S. Saurabh, and Y. Villange. Local search: Is brute-force avoidable? Journal of Computer and System Sciences, 78(3):707-719, 2012. Google Scholar
  12. Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci., 410(1):53-61, 2009. Google Scholar
  13. F. V. Fomin, D. Lokshtanov, F. Panolan, and S. Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM, 63(4):29:1-29:60, 2016. Google Scholar
  14. D. Gale and L. S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  15. D. Gusfield and R. W. Irving. The stable marriage problem: structure and algorithms. MIT press, 1989. Google Scholar
  16. R. W. Irving and D. Manlove. Finding large stable matchings. ACM Journal of Experimental Algorithmics, 2009. Google Scholar
  17. H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack problems. Springer, 2004. Google Scholar
  18. S. Khuller, R. Bhatia, and R. Pless. On local search and placement of meters in networks. SIAM journal on computing, 32(2):470-487, 2003. Google Scholar
  19. D. E. Knuth. Marriages stables. Technical report, 1976. Google Scholar
  20. A. Krokhin and D. Marx. On the hardness of losing weight. ACM Transactions on Algorithms, 8(2):1-18, 2012. Google Scholar
  21. D. Manlove. Algorithmics of matching under preferences, volume 2. World Scientific, 2013. Google Scholar
  22. D. F. Manlove, I. McBride, and J. Trimble. "Almost-stable" matchings in the Hospitals/Residents problem with couples. Constraints, 22(1):50-72, 2017. Google Scholar
  23. D. Marx. Local search. Parameterized Complexity News, 3:7-8, 2008. Google Scholar
  24. D. Marx. Searching the k-change neighborhood for TSP is W[1]-hard. Operations Research Letters, 36(1):31-36, 2008. Google Scholar
  25. D. Marx and I. Schlotter. Parameterized complexity and local search approaches for the stable marriage problem with ties. Algorithmica, 58(1):170-187, 2010. Google Scholar
  26. D. Marx and I. Schlotter. Stable assignment with couples: Parameterized complexity and local search. Discrete Optimization, 8(1):25-40, 2011. Google Scholar
  27. S. Micali and V. V. Vazirani. An O(√|V||E|) algorithm for finding maximum matching in general graphs. In Foundations of Computer Science (FOCS), pages 17-27, 1980. Google Scholar
  28. R. Neidermeier. Invitation to fixed-parameter algorithms. Springer, 2006. Google Scholar
  29. Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci., 67(4):757-771, 2003. Google Scholar
  30. A. E. Roth. The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy, 92(6), 1984. Google Scholar
  31. A. E. Roth. On the allocation of residents to rural hospitals: A general property of two-sided matching markets. Econometrica: Journal of the Econometric Society, 54(2):425-427, 1986. Google Scholar
  32. S. Szeider. The parameterized complexity of k-flip local search for sat and max sat. Discrete Optimization, 8(1):139-145, 2011. Google Scholar
  33. El-Ghazali Talbi. Metaheuristics: From design to implementation, volume 74. John Wiley & Sons, 2009. Google Scholar
  34. K. Tomoeda. Finding a stable matching under type-specific minimum quotas. Journal of Economic Theory, 176:81-117, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact