Document Open Access Logo

Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters

Authors Robert Bredereck , Klaus Heeger , Dušan Knop , Rolf Niedermeier

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.44.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Robert Bredereck
  • Technische Universität Berlin, Chair of Algorithmics and Computational Complexity, Germany
Klaus Heeger
  • Technische Universität Berlin, Chair of Algorithmics and Computational Complexity, Germany
Dušan Knop
  • Technische Universität Berlin, Chair of Algorithmics and Computational Complexity, Germany
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic
Rolf Niedermeier
  • Technische Universität Berlin, Chair of Algorithmics and Computational Complexity, Germany

Funding

Main work was done while all authors were with TU Berlin.
  • Heeger, Klaus: Supported by DFG Research Training Group 2434 "Facets of Complexity".
  • Knop, Dušan: Supported by the DFG, project MaMu (NI 369/19).

Cite AsGet BibTex

Robert Bredereck, Klaus Heeger, Dušan Knop, and Rolf Niedermeier. Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.44

Abstract

We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem Stable Marriage which focuses on a bipartite scenario, Stable Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded feedback vertex number (these are each time the respective parameters). However, if we "only" ask for perfect stable matchings or the mere existence of a stable matching, then we obtain fixed-parameter tractability with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Matchings and factors
Keywords
  • Stable matching
  • acceptability graph
  • fixed-parameter tractability
  • W[1]-hardness
  • treewidth
  • treedepth
  • tree-cut width
  • feedback set numbers

Metrics

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

Related Versions

References

  1. Deeksha Adil, Sushmita Gupta, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. Parameterized algorithms for stable matching with ties and incomplete lists. Theor. Comput. Sci., 723:1-10, 2018. Google Scholar
  2. John J. Bartholdi III and Michael Trick. Stable Matching with Preferences Derived from a Psychological Model. Oper. Res. Lett., 5(4):165-169, 1986. Google Scholar
  3. Robert Bredereck, Jiehua Chen, Ugo Paavo Finnendahl, and Rolf Niedermeier. Stable Roommate with Narcissistic, Single-Peaked, and Single-Crossing Preferences. In Proc. of ADT '17, volume 10576 of LNCS, pages 315-330. Springer, 2017. Google Scholar
  4. Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems. Information and Computation, 201(2):216-231, 2005. Google Scholar
  5. Jiehua Chen, Danny Hermelin, Manuel Sorge, and Harel Yedidsion. How Hard Is It to Satisfy (Almost) All Roommates? In Proc. of ICALP '18, volume 107 of LIPIcs, pages 35:1-35:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  6. Jiehua Chen, Rolf Niedermeier, and Piotr Skowron. Stable Marriage with Multi-Modal Preferences. In Proc. of EC '18, pages 269-286. ACM, 2018. Google Scholar
  7. Ágnes Cseh, Robert W. Irving, and David F. Manlove. The Stable Roommates Problem with Short Lists. Theory Comput. Syst., 63(1):128-149, 2019. Google Scholar
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  9. Tomás Feder. A new fixed point approach for stable networks and stable marriages. J. Comput. Syst. Sci., 45(2):233-284, 1992. Google Scholar
  10. Anh-Tuan Gai, Dmitry Lebedev, Fabien Mathieu, Fabien de Montgolfier, Julien Reynier, and Laurent Viennot. Acyclic Preference Systems in P2P Networks. In Proc. of Euro-Par '07, volume 4641 of LNCS, pages 825-834. Springer, 2007. Google Scholar
  11. Robert Ganian, Eun Jung Kim, and Stefan Szeider. Algorithmic Applications of Tree-Cut Width. In Proc. of MFCS '15, volume 9235 of LNCS, pages 348-360. Springer, 2015. Google Scholar
  12. Robert Ganian, Fabian Klute, and Sebastian Ordyniak. On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem. In Proc. of STACS '18, volume 96 of LIPIcs, pages 33:1-33:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  13. Robert Ganian, Neha Lodha, Sebastian Ordyniak, and Stefan Szeider. SAT-encodings for treecut width and treedepth. In Proc. of ALENEX '19, pages 117-129. SIAM, 2019. Google Scholar
  14. Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos. Lean Tree-Cut Decompositions: Obstructions and Algorithms. In Proc. of STACS '19, volume 126 of LIPIcs, pages 32:1-32:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  15. Sushmita Gupta, Saket Saurabh, and Meirav Zehavi. On Treewidth and Stable Marriage. CoRR, abs/1707.05404, 2017. URL: http://arxiv.org/abs/1707.05404.
  16. Dan Gusfield and Robert W. Irving. The Stable Marriage Problem - Structure and Algorithms. MIT Press, 1989. Google Scholar
  17. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  18. Robert W. Irving. An Efficient Algorithm for the "Stable Roommates" Problem. J. Algorithms, 6(4):577-595, 1985. Google Scholar
  19. Kazuo Iwama, Shuichi Miyazaki, Yasufumi Morita, and David Manlove. Stable Marriage with Incomplete Lists and Ties. In Proc. of ICALP '99, volume 1644 of LNCS, pages 443-452. Springer, 1999. Google Scholar
  20. Eun Jung Kim, Sang-il Oum, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos. An FPT 2-Approximation for Tree-Cut Decomposition. Algorithmica, 80(1):116-135, 2018. Google Scholar
  21. Ton Kloks. Treewidth, Computations and Approximations, volume 842 of LNCS. Springer, 1994. URL: https://doi.org/10.1007/BFb0045375.
  22. Christian Komusiewicz and Rolf Niedermeier. New Races in Parameterized Algorithmics. In Proc. of MFCS '12, volume 7464 of LNCS, pages 19-30. Springer, 2012. Google Scholar
  23. David Manlove. The structure of stable marriage with indifference. Discrete Appl. Math., 122(1-3):167-181, 2002. Google Scholar
  24. David Manlove, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki, and Yasufumi Morita. Hard variants of stable marriage. Theor. Comput. Sci., 276(1-2):261-279, 2002. Google Scholar
  25. David F. Manlove. Algorithmics of Matching Under Preferences, volume 2 of Series on Theoretical Computer Science. WorldScientific, 2013. Google Scholar
  26. Dániel Marx and Ildikó Schlotter. Parameterized Complexity and Local Search Approaches for the Stable Marriage Problem with Ties. Algorithmica, 58(1):170-187, 2010. Google Scholar
  27. Dániel Marx and Paul Wollan. Immersions in Highly Edge Connected Graphs. SIAM J. Discrete Math., 28(1):503-520, 2014. Google Scholar
  28. Dániel Marx and Ildikó Schlotter. Stable assignment with couples: Parameterized complexity and local search. Discrete Optim., 8(1):25-40, 2011. Google Scholar
  29. Eric McDermid. A 3/2-Approximation Algorithm for General Stable Marriage. In Proc. of ICALP '09, pages 689-700. Springer, 2009. Google Scholar
  30. Kitty Meeks and Baharak Rastegari. Stable Marriage with Groups of Similar Agents. In Proc. of WINE '18, volume 11316 of LNCS, pages 312-326. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-04612-5_21.
  31. Matthias Mnich and Ildikó Schlotter. Stable Marriage with Covering Constraints-A Complete Computational Trichotomy. In Proc. of SAGT '17, volume 10504 of LNCS, pages 320-332. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-66700-3_25.
  32. Eytan Ronn. NP-complete stable matching problems. J. Algorithms, 11(2):285-304, 1990. Google Scholar
  33. Alvin E. Roth, Tayfun Sönmez, and M. Utku Ünver. Pairwise kidney exchange. J. Econ. Theory, 125(2):151-188, 2005. Google Scholar
  34. Alvin E. Roth, Tayfun Sönmez, and M. Utku Ünver. Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences. Am. Econ. Rev., 97(3):828-851, June 2007. Google Scholar
  35. Paul Wollan. The structure of graphs not admitting a fixed immersion. J. Comb. Theory, Ser. B, 110:47-66, 2015. URL: https://doi.org/10.1016/j.jctb.2014.07.003.
  36. H. Yanagisawa. Approximation Algorithms for Stable Marriage Problems. PhD thesis, Kyoto University, 2007. 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