{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:41:27Z","timestamp":1787323287399,"version":"build-2736575974"},"reference-count":50,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100001502","name":"Department of Atomic Energy, Government of India","doi-asserted-by":"publisher","award":["RTI4001"],"award-info":[{"award-number":["RTI4001"]}],"id":[{"id":"10.13039\/501100001502","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101039913"],"award-info":[{"award-number":["101039913"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A matching is a subset of edges in a graph [Formula: see text] that do not share an endpoint. A matching [Formula: see text] is a [Formula: see text] -matching if the subgraph of [Formula: see text] induced by the endpoints of the edges of [Formula: see text] satisfies property [Formula: see text]. For example, if the property [Formula: see text] is that of being a matching, being acyclic, or being disconnected, then we obtain an induced matching, an acyclic matching, and a disconnected matching, respectively. Given a graph [Formula: see text] and a positive integer [Formula: see text], the [Formula: see text] Matching problem asks whether [Formula: see text] has a [Formula: see text]-matching of size at least [Formula: see text]. In this paper, we analyze the [Formula: see text] Matching problems from the viewpoint of Parameterized Complexity with respect to the parameter treewidth. In particular, we present a deterministic algorithm solving Induced Matching in [Formula: see text] time and a randomized algorithm solving Acyclic Matching in [Formula: see text] time. For any fixed [Formula: see text], [Formula: see text]-Disconnected Matching can be solved in [Formula: see text] time by a deterministic algorithm. Additionally, assuming the Exponential Time Hypothesis, we show that Disconnected Matching has no [Formula: see text]-time algorithm.<\/jats:p>","DOI":"10.1137\/23m160013x","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T03:36:24Z","timestamp":1749440184000},"page":"1280-1311","source":"Crossref","is-referenced-by-count":3,"title":["\\(\\mathcal{P}\\)-Matchings Parameterized by Treewidth"],"prefix":"10.1137","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5560-9129","authenticated-orcid":true,"given":"Juhi","family":"Chaudhary","sequence":"first","affiliation":[{"name":"School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of the Negev, Beersheba, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.1010"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2020.04.005"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"J. Baste, M. F\u00fcrst, and D. Rautenbach, Approximating maximum acyclic matchings by greedy and local search strategies, in Computing and Combinatorics: 26th International Conference, COCOON 2020, Springer, 2020, pp. 542\u2013553.","DOI":"10.1007\/978-3-030-58150-3_44"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.01.002"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68705-6_8"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22429"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"A. Bj\u00f6rklund, T. Husfeldt, P. Kaski, and M. Koivisto, Fourier meets M\u00f6bius: Fast subset convolution, in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, 2007, pp. 67\u201374.","DOI":"10.1145\/1250790.1250801"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"ref9","first-page":"1","volume":"11","author":"Bodlaender H. L.","year":"1993","journal-title":"Acta Cybernet."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90275-F"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36478-1_5"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00803-8"},{"key":"ref13","volume-title":"Graph-Theoretic Concepts in Computer Science, 49th International Workshop","author":"Chaudhary J.","year":"2023"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/20M1330609"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1145\/3506707"},{"key":"ref17","series-title":"Grad. Texts in Math. 173","volume-title":"Graph Theory","author":"Diestel R.","year":"2012"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.05.013"},{"key":"ref20","unstructured":"P. Erd\u0151s and J. Ne\u0161et\u0159il, Irregularities of partitions, G. Hal\u00e1sz and V. T. S\u00f3s, eds. Springer, Berlin, Heidelberg, 1989, pp. 162\u2013163."},{"key":"ref21","first-page":"205","volume":"29","author":"Faudree R. J.","year":"1990","journal-title":"Ars Combin."},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/16M1074631"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-019-03311-1"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2004.08.027"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.11.038"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0004-z"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00194-8"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.113821"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.113862"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00904-w"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019828371X"},{"key":"ref34","unstructured":"T. Koana, Induced matching below guarantees: Average paves the way for fixed-parameter tractability, in Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, STACS, 2023."},{"key":"ref35","doi-asserted-by":"crossref","unstructured":"M. Lampis and M. Vasilakis, Structural parameterizations for induced and acyclic matching, in Proceedings of the WG 51st International Workshop on Graph-Theoretic Concepts in Computer Science Conference, 2025.","DOI":"10.1007\/978-3-032-11835-6_26"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1137\/16M1104834"},{"key":"ref37","series-title":"Ann. Discrete Math. 29","volume-title":"Matching Theory","author":"Lov\u00e1sz L.","year":"1986"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1142\/8591"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"S. Micali and V. V. Vazirani, An O\\((\\sqrt {|V|}|e|)\\) algorithm for finding maximum matching in general graphs, in 21st Annual Symposium on Foundations of Computer Science (sfcs 1980), IEEE, 1980, pp. 17\u201327.","DOI":"10.1109\/SFCS.1980.12"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.07.011"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.09.005"},{"key":"ref42","doi-asserted-by":"crossref","unstructured":"K. Mulmuley, U. V. Vazirani, and V. V. Vazirani, Matching is as easy as matrix inversion, in Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 1987, pp. 345\u2013354.","DOI":"10.1145\/28395.383347"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.12.008"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830912500504"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1515\/gmj-2021-2090"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90077-1"},{"key":"ref48","first-page":"25","volume":"3","author":"Vizing V. G.","year":"1964","journal-title":"Diskret. Analiz."},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.09.026"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46784-X_10"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M160013X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:53:08Z","timestamp":1787320388000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M160013X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1137\/23M160013X"],"URL":"https:\/\/doi.org\/10.1137\/23m160013x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}