{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T23:21:44Z","timestamp":1789168904302,"version":"build-2803163510"},"reference-count":66,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA-01\/2017-18"]}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:p>Stable Marriage is a fundamental problem to both computer science and economics. Four well-known NP-hard optimization versions of this problem are the Sex-Equal Stable Marriage (SESMI), Balanced Stable Marriage (BSMI), max-Stable Marriage with Ties (max-SMTI), and min-Stable Marriage with Ties (min-SMTI) problems. In this paper, we analyze these problems from the viewpoint of parameterized complexity. We conduct the first study of these problems in particular, and of problems related to Stable Marriage in general, with respect to the parameter treewidth. The motivation behind the choice of treewidth is threefold. First, several problems in social choice theory have already been studied with respect to treewidth. The networks relevant to these problems (say, social networks) are clearly also relevant to Stable Marriage. Thus, the motivation underlying these studies directly extends to our study. Second, empirical studies of the treewidth of several types of networks relevant to Stable Marriage have also already been undertaken, identifying that some of these networks indeed have a treelike structure. Third, treewidth is the most well studied structural parameter in parameterized complexity. We design optimal parameterized algorithms for all four problems under the treewidth of both their primal graphs and rotation digraphs. First, we study the treewidth ${\\mathtt{tw}}$ of the primal graph. We establish that all four problems are W[1]-hard. In particular, while it is easy to show that all four problems admit algorithms that run in time $n^{{\\mathcal{O}}({\\mathtt{tw}})}$, we prove that unless the exponential-time hypothesis is false, all of these algorithms are optimal. Next, we study the treewidth ${\\mathtt{tw}}$ of the rotation digraph. In this context, max-SMTI and min-SMTI are not defined. For both SESMI and BSMI, we design (highly nontrivial) algorithms that run in time $2^{{\\mathtt{tw}}}n^{{\\mathcal{O}}(1)}$. Then, for both SESMI and BSMI, we prove that unless the strong exponential-time hypothesis is false, algorithms that run in time $(2-\\epsilon)^{{\\mathtt{tw}}}n^{{\\mathcal{O}}(1)}$ do not exist for any fixed $\\epsilon&gt;0$. We thus present a comprehensive, complete picture of the behavior of Stable Marriage with respect to treewidth.<\/jats:p>","DOI":"10.1137\/19m130491x","type":"journal-article","created":{"date-parts":[[2022,3,11]],"date-time":"2022-03-11T11:11:27Z","timestamp":1646997087000},"page":"596-681","source":"Crossref","is-referenced-by-count":4,"title":["On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization)"],"prefix":"10.1137","volume":"36","author":[{"given":"Sushmita","family":"Gupta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,3,9]]},"reference":[{"key":"atypb1","first-page":"1","author":"Adcock A. B.","year":"2013","journal-title":"Tx"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2016.1182952"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.03.015"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(86)90072-6"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"O. Ben-Zwi, D. Hermelin, D. Lokshtanov, and I. Newman,\n                      An exact almost optimal algorithm for target set selection in social networks\n                      , in Proceedings of the 10th ACM Conference on Electronic Commerce, Stanford, CA, 2009, pp. 355-362.","DOI":"10.1145\/1566374.1566424"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"atypb7","first-page":"95","author":"Bousquet N.","year":"2015","journal-title":"OR"},{"key":"atypb8","first-page":"315","author":"Bredereck R.","year":"2017","journal-title":"Luxembourg"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-012-0717-8"},{"key":"atypb10","first-page":"252","author":"Calabro C.","year":"2006","journal-title":"Prague"},{"key":"atypb11","first-page":"75","author":"Calabro C.","year":"2009","journal-title":"Copenhagen"},{"key":"atypb12","unstructured":"J. Chen, D. Hermelin, M. Sorge, and H. Yedidsion,\n                      How Hard Is It to Satisfy (Almost) All Roommates?\n                      ,https:\/\/arxiv.org\/abs\/1707.04316, 2017."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/2925416"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb15","unstructured":"B. Dean and R. Jalasutram,\n                      Factor revealing lps and stable matching with ties and incomplete lists\n                      , in Proceedings of the 3rd International Workshop on Matching Under Preferences, 2015, pp. 989-996."},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 4th ed., Grad. Texts in Math. 173, Springer, New York, 2012.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts Comput. Sci., Springer, New York, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb18","unstructured":"E. Elkind, M. Lackner, and D. Peters,\n                      Structured preferences\n                      , Trends Comput. Social Choice, (2017), pp. 107-207."},{"key":"atypb19","unstructured":"T. Feder,\n                      Stable Networks and Product Graphs\n                      , Ph.D. thesis, Stanford University, 1990."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90048-N"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.065"},{"key":"atypb22","unstructured":"J. Flum and M. Grohe,\n                      Parameterized Complexity Theory\n                      , Texts Theoret. Comput. Sci., Springer, New York, 2006."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90074-5"},{"key":"atypb25","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W. H. Freeman, New York, 1979."},{"key":"atypb26","unstructured":"I. P. Gent and P. Prosser,\n                      An empirical study of the stable marriage problem with ties and incomplete lists\n                      , in Proceedings of the 15th European Conference on Artificial Intelligence, IOS Press, 2002, pp. 141-145."},{"key":"atypb27","first-page":"989","author":"Giannakopoulos I.","year":"2015","journal-title":"Proceedings of the IEEE 27th International Conference on Tools with Artificial Intelligence"},{"key":"atypb28","unstructured":"S. Gupta, S. Roy, S. Saurabh, and M. Zehavi,\n                      Balanced Stable Marriage: How Close Is Close Enough?\n                      ,http:\/\/arxiv.org\/abs\/1707.09545, 2017."},{"key":"atypb29","first-page":"106","author":"Gupta S.","year":"2017","journal-title":"Italy"},{"key":"atypb30","unstructured":"D. Gusfield and R. W. Irving,\n                      The Stable Marriage Problem: Structure and Algorithms\n                      , Foundations of Computing Series, MIT Press, Cambridge, MA, 1989."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00321-9"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0923-0"},{"key":"atypb33","first-page":"1575","author":"Igarashi A.","year":"2017","journal-title":"Brazil"},{"key":"atypb34","first-page":"565","author":"Igarashi A.","year":"2017","journal-title":"San Francisco"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00206-7"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)00179-P"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/0215048"},{"key":"atypb40","first-page":"532","volume":"34","author":"Irving R. W.","year":"1987","journal-title":"stable marriage, J. ACM"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.09.003"},{"key":"atypb42","first-page":"131","author":"Iwama K.","year":"2008","journal-title":"Proceedings of the International Conference on Informatics Education and Research for Knowledge-Circulating Society"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868239"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/BF03167200"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9371-7"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.3390\/a6030471"},{"key":"atypb47","doi-asserted-by":"crossref","unstructured":"D. E. Knuth,\n                      Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms\n                      , CRM Proc. Lecture Notes, AMS, Providence, RI, 1997.","DOI":"10.1090\/crmp\/010"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00322-5"},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"D. F. Manlove,\n                      Algorithmics of Matching Under Preferences\n                      , Ser. Theoret. Comput. Sci., World Scientific, Englewood Cliffs, NJ, 2013.","DOI":"10.1142\/8591"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9326-z"},{"key":"atypb51","doi-asserted-by":"crossref","unstructured":"E. McDermid,\n                      A 3\/2-approximation algorithm for general stable marriage\n                      , in Proceedings of ICALP'09, 2009, pp. 689-700.","DOI":"10.1007\/978-3-642-02927-1_57"},{"key":"atypb52","unstructured":"E. McDermid,\n                      A Structural Approach to Matching Problems with Preferences\n                      , Ph.D. thesis, University of Glasgow, 2011."},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9672-0"},{"key":"atypb54","doi-asserted-by":"crossref","unstructured":"R. Meir, Y. Zick, E. Elkind, and J. S. Rosenschein,\n                      Bounding the cost of stability in games over interaction networks\n                      , in Proceedings of the 27th AAAI Conference on Artificial Intelligence, Bellevue, WA, 2013.","DOI":"10.1609\/aaai.v27i1.8613"},{"key":"atypb55","doi-asserted-by":"crossref","unstructured":"D. Munera, D. Diaz, S. Abreu, F. Rossi, V. Saraswat, and P. Codognet,\n                      Solving hard stable matching problems via local search and cooperative parallelization\n                      , in Proceedings of the 29th AAAI Conference on Artificial Intelligence, 2015.","DOI":"10.1609\/aaai.v29i1.9360"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1109\/ISCAS.1995.521562"},{"key":"atypb57","doi-asserted-by":"crossref","unstructured":"R. Niedermeier,\n                      Invitation to Fixed-Parameter Algorithms\n                      , Oxford Lecture Ser. Math. Appl., Oxford University Press, Oxford, UK, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"atypb58","unstructured":"G. O'Malley,\n                      Algorithmic Aspects of Stable Matching Problems\n                      , Ph.D. thesis, University of Glasgow, 2007."},{"key":"atypb59","first-page":"586","author":"Peters D.","year":"2016","journal-title":"AZ"},{"key":"atypb60","first-page":"594","author":"Peters D.","year":"2016","journal-title":"AZ"},{"key":"atypb61","first-page":"137","volume":"3","author":"A","year":"1998","journal-title":"Rev. Econ. Des."},{"key":"atypb62","first-page":"457","author":"Vien N. A.","year":"2007","journal-title":"Computing Sciences and Software Engineering"},{"key":"atypb63","unstructured":"H. Yanagisawa,\n                      Algorithms for Stable Marriage Problems\n                      , Master's thesis, Kyoto University, School of Informatics, 2003."},{"key":"atypb64","first-page":"77","author":"Yang Y.","year":"2015","journal-title":"Istanbul"},{"key":"atypb65","first-page":"1178","author":"Yang Y.","year":"2017","journal-title":"Brazil"},{"key":"atypb66","first-page":"425","author":"Yu L.","year":"2013","journal-title":"Beijing"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M130491X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:13:35Z","timestamp":1787318015000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M130491X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["10.1137\/19M130491X"],"URL":"https:\/\/doi.org\/10.1137\/19m130491x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3]]}}}