{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T18:14:10Z","timestamp":1762107250898,"version":"build-2065373602"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T00:00:00Z","timestamp":1722470400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T00:00:00Z","timestamp":1722988800000},"content-version":"vor","delay-in-days":6,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001405","name":"Tata Institute of Fundamental Research","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001405","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,8]]},"abstract":"Abstract<\/jats:title>Low-Acy-Matching<\/jats:sc> asks to find a maximal matching M<\/jats:italic> in a given graph G<\/jats:italic> of minimum cardinality such that the set of M<\/jats:italic>-saturated vertices induces an acyclic subgraph in G<\/jats:italic>. The decision version of Low-Acy-Matching<\/jats:sc> is known to be $${\\textsf{NP}}$$<\/jats:tex-math>\n NP<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete. In this paper, we strengthen this result by proving that the decision version of Low-Acy-Matching<\/jats:sc> remains $${\\textsf{NP}}$$<\/jats:tex-math>\n NP<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete for bipartite graphs with maximum degree 6 and planar perfect elimination bipartite graphs. We also show the hardness difference between Low-Acy-Matching<\/jats:sc> and Max-Acy-Matching<\/jats:sc>. Furthermore, we prove that, even for bipartite graphs, Low-Acy-Matching<\/jats:sc> cannot be approximated within a ratio of $$n^{1-\\epsilon }$$<\/jats:tex-math>\n \n n<\/mml:mi>\n \n 1<\/mml:mn>\n -<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for any $$\\epsilon >0$$<\/jats:tex-math>\n \n \u03f5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> unless $${\\textsf{P}}={\\textsf{NP}}$$<\/jats:tex-math>\n \n P<\/mml:mi>\n =<\/mml:mo>\n NP<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Finally, we establish that Low-Acy-Matching<\/jats:sc> exhibits $$\\textsf{APX}$$<\/jats:tex-math>\n APX<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hardness when restricted to 4-regular graphs.\n<\/jats:p>","DOI":"10.1007\/s10878-024-01200-3","type":"journal-article","created":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T11:07:15Z","timestamp":1723028835000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the complexity of minimum maximal acyclic matchings"],"prefix":"10.1007","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5560-9129","authenticated-orcid":false,"given":"Juhi","family":"Chaudhary","sequence":"first","affiliation":[]},{"given":"Sounaka","family":"Mishra","sequence":"additional","affiliation":[]},{"given":"B. S.","family":"Panda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,7]]},"reference":[{"key":"1200_CR1","volume-title":"Complexity and approximation: combinatorial optimization problems and their approximability properties","author":"G Ausiello","year":"2012","unstructured":"Ausiello G, Crescenzi P, Gambosi G, Kann V, Spaccamela AM, Protasi M (2012) Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer, New York"},{"key":"1200_CR2","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2017.05.042","volume":"717","author":"C Bazgan","year":"2018","unstructured":"Bazgan C, Brankovic L, Casel K, Fernau H, Jansen K, Klein K, Lampis M, Liedloff M, Monnot J, Paschos VT (2018) The many facets of upper domination. Theoret Comput Sci 717:2\u201325","journal-title":"Theoret Comput Sci"},{"key":"1200_CR3","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.dam.2014.06.001","volume":"196","author":"N Boria","year":"2015","unstructured":"Boria N, Croce FD, Paschos VT (2015) On the max min vertex cover problem. Discret Appl Math 196:62\u201371","journal-title":"Discret Appl Math"},{"key":"1200_CR4","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0166-218X(92)90275-F","volume":"24","author":"K Cameron","year":"1989","unstructured":"Cameron K (1989) Induced matchings. Discret Appl Math 24:97\u2013102","journal-title":"Discret Appl Math"},{"key":"1200_CR5","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.tcs.2021.05.036","volume":"882","author":"J Chaudhary","year":"2021","unstructured":"Chaudhary J, Panda BS (2021) On the complexity of minimum maximal uniquely restricted matching. Theoret Comput Sci 882:15\u201328","journal-title":"Theoret Comput Sci"},{"key":"1200_CR6","doi-asserted-by":"crossref","unstructured":"Chaudhary J, Mishra S, Panda BS (2022) On the complexity of minimum maximal acyclic matching. In: Proceedings of the 28th International computing and combinatorics conference mathematics, Lecture Notes in Computer Science, vol 13595. Springer, pp 106\u2013117","DOI":"10.1007\/978-3-031-22105-7_10"},{"key":"1200_CR7","doi-asserted-by":"crossref","unstructured":"Chaudhary J, Mishra S, Panda BS (2023) Minimum maximal acyclic matching in proper interval graphs. In: Proceedings of the 9th Annual International conference on algorithms and discrete applied mathematics, Lecture Notes in Computer Science, vol 13947. Springer, pp 377\u2013388","DOI":"10.1007\/978-3-031-25211-2_29"},{"key":"1200_CR8","doi-asserted-by":"crossref","unstructured":"Chaudhary J, Zehavi M (2023a) $$\\cal{P}$$-Matchings parameterized by Treewidth. In: Proceedings of the 49th International workshop on graph-theoretic concepts in computer science, Lecture Notes in Computer Science, vol 14093. Springer, pp 217\u2013231","DOI":"10.1007\/978-3-031-43380-1_16"},{"key":"1200_CR9","doi-asserted-by":"crossref","unstructured":"Chaudhary J, Zehavi M (2023b) Parameterized results on acyclic matchings with implications for related problems. In: Proceedings of the 49th International workshop on graph-theoretic concepts in computer science, Lecture Notes in Computer Science, vol 14093. Springer, pp 201\u2013216","DOI":"10.1007\/978-3-031-43380-1_15"},{"issue":"1","key":"1200_CR10","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.disopt.2010.02.006","volume":"8","author":"P Damaschke","year":"2011","unstructured":"Damaschke P (2011) Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover. Discret Optim 8(1):18\u201324","journal-title":"Discret Optim"},{"key":"1200_CR11","unstructured":"Dublois L, Hanaka T, Ghadikolaei MK, Lampis M, Melissinos N (2020) (In)approximability of maximum minimal FVS. In: Proceedings of the 31st International symposium on algorithms and computation (ISAAC), vol 181 of LIPIcs, pp 3:1\u201314"},{"key":"1200_CR12","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds J (1965) Paths, trees, and flowers. Can J Math 17:449\u2013467","journal-title":"Can J Math"},{"issue":"1","key":"1200_CR13","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1137\/16M1074631","volume":"32","author":"MC Francis","year":"2018","unstructured":"Francis MC, Jacob D, Jana S (2018) Uniquely restricted matchings in interval graphs. SIAM J Discret Math 32(1):148\u2013172","journal-title":"SIAM J Discret Math"},{"key":"1200_CR14","unstructured":"F\u00fcrst M (2019) Restricted matchings. PhD thesis, Universit\u00e4t Ulm"},{"issue":"1\u20132","key":"1200_CR15","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s10479-019-03311-1","volume":"279","author":"M F\u00fcrst","year":"2019","unstructured":"F\u00fcrst M, Rautenbach D (2019) On some hard and some tractable cases of the maximum acyclic matching problem. Ann Oper Res 279(1\u20132):291\u2013300","journal-title":"Ann Oper Res"},{"key":"1200_CR16","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, New York"},{"issue":"7","key":"1200_CR17","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1016\/j.disc.2012.11.031","volume":"313","author":"W Goddard","year":"2013","unstructured":"Goddard W, Henning MA (2013) Independent domination in graphs: a survey and recent results. Discret Math 313(7):839\u2013854","journal-title":"Discret Math"},{"issue":"1\u20133","key":"1200_CR18","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.disc.2004.08.027","volume":"293","author":"W Goddard","year":"2005","unstructured":"Goddard W, Hedetniemi SM, Hedetniemi ST, Laskar R (2005) Generalized subgraph-restricted matchings in graphs. Discret Math 293(1\u20133):129\u2013138","journal-title":"Discret Math"},{"issue":"2","key":"1200_CR19","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1002\/jgt.3190020209","volume":"2","author":"MC Golumbic","year":"1978","unstructured":"Golumbic MC, Goss CF (1978) Perfect elimination and chordal bipartite graphs. J Graph Theory 2(2):155\u2013163","journal-title":"J Graph Theory"},{"issue":"2","key":"1200_CR20","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00453-001-0004-z","volume":"31","author":"MC Golumbic","year":"2001","unstructured":"Golumbic MC, Hirst T, Lewenstein M (2001) Uniquely restricted matchings. Algorithmica 31(2):139\u2013154","journal-title":"Algorithmica"},{"key":"1200_CR21","doi-asserted-by":"crossref","unstructured":"Gomes GCM, Masquio BP, Pinto PED, dos Santos VF, Szwarcfiter JL (2022) Weighted connected matchings. In: Proceedings of the 15th Latin American theoretical informatics symposium, Springer, pp 54\u201370","DOI":"10.1007\/978-3-031-20624-5_4"},{"key":"1200_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.113821","volume":"956","author":"GCM Gomes","year":"2023","unstructured":"Gomes GCM, Masquio BP, Pinto PED, dos Santos VF, Szwarcfiter JL (2023) Disconnected matchings. Theoret Comput Sci 956:113821","journal-title":"Theoret Comput Sci"},{"key":"1200_CR23","unstructured":"Kann V (1992) On the approximability of NP-complete optimization problems. PhD thesis, Royal Institute of Technology Stockholm"},{"issue":"4","key":"1200_CR24","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1137\/0208049","volume":"8","author":"MS Krishnamoorthy","year":"1979","unstructured":"Krishnamoorthy MS, Deo NS (1979) Node-deletion NP-complete problems. SIAM J Comput 8(4):619\u2013625","journal-title":"SIAM J Comput"},{"key":"1200_CR25","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.endm.2006.06.019","volume":"24","author":"VV Lepin","year":"2006","unstructured":"Lepin VV (2006) A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree. Electron Notes Discret Math 24:111\u2013116","journal-title":"Electron Notes Discret Math"},{"key":"1200_CR26","volume-title":"Matching theory","author":"L Lov\u00e1sz","year":"2009","unstructured":"Lov\u00e1sz L, Plummer MD (2009) Matching theory, vol 367. American Mathematical Society, Michigan"},{"key":"1200_CR27","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/j.endm.2011.05.059","volume":"37","author":"S Mishra","year":"2011","unstructured":"Mishra S (2011) On the maximum uniquely restricted matching for bipartite graphs. Electron Notes Discret Math 37:345\u2013350","journal-title":"Electron Notes Discret Math"},{"key":"1200_CR28","unstructured":"Orlovich YL, Zverovich IE (2004) Maximal induced matchings of minimum\/maximum size. In: Technical report, DIMACS TR 2004-26"},{"issue":"3","key":"1200_CR29","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1016\/j.disopt.2007.11.010","volume":"5","author":"YL Orlovich","year":"2008","unstructured":"Orlovich YL, Finke G, Gordon V, Zverovich I (2008) Approximability results for the maximum and minimum maximal induced matching problems. Discret Optim 5(3):584\u2013593","journal-title":"Discret Optim"},{"key":"1200_CR30","doi-asserted-by":"crossref","unstructured":"Panda BS, Pandey A (2016) On the complexity of minimum cardinality maximal uniquely restricted matching in graphs. In: International conference on theoretical computer science and discrete mathematics, Lecture Notes in Computer Science, vol 10398. Springer, pp 218\u2013227","DOI":"10.1007\/978-3-319-64419-6_29"},{"key":"1200_CR31","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.tcs.2022.12.008","volume":"943","author":"BS Panda","year":"2023","unstructured":"Panda BS, Chaudhary J (2023) Acyclic matching in some subclasses of graphs. Theoret Comput Sci 943:36\u201349","journal-title":"Theoret Comput Sci"},{"issue":"3","key":"1200_CR32","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou CH, Yannakakis M (1991) Optimization, approximation, and complexity classes. J Comput Syst Sci 43(3):425\u2013440","journal-title":"J Comput Syst Sci"},{"key":"1200_CR33","doi-asserted-by":"crossref","unstructured":"Saffren S, Angel D (2022) Acyclic matching on hypercube networks. In: Proceedings of the 3rd International conference on intelligent computing instrumentation. IEEE, pp 681\u2013685","DOI":"10.1109\/ICICICT54557.2022.9917684"},{"issue":"1","key":"1200_CR34","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0020-0190(82)90077-1","volume":"15","author":"LJ Stockmeyer","year":"1982","unstructured":"Stockmeyer LJ, Vazirani VV (1982) NP-completeness of some generalizations of the maximum matching problem. Inf Process Lett 15(1):14\u201319","journal-title":"Inf Process Lett"},{"issue":"1","key":"1200_CR35","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"CA Tovey","year":"1984","unstructured":"Tovey CA (1984) A simplified NP-complete satisfiability problem. Discret Appl Math 8(1):85\u201389","journal-title":"Discret Appl Math"},{"issue":"3","key":"1200_CR36","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis M, Gavril F (1980) Edge dominating sets in graphs. SIAM J Appl Math 38(3):364\u2013372","journal-title":"SIAM J Appl Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01200-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01200-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01200-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T19:12:08Z","timestamp":1724440328000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01200-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["1200"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01200-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,8]]},"assertion":[{"value":"18 July 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"10"}}