{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T06:19:18Z","timestamp":1782368358155,"version":"3.54.5"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The well-known -complete problem <jats:sc>Matching Cut<\/jats:sc> is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for <jats:sc>Matching Cut<\/jats:sc> restricted to <jats:italic>H<\/jats:italic>-free graphs, that is, graphs that do not contain some fixed graph\u00a0<jats:italic>H<\/jats:italic> as an induced subgraph. We also prove new complexity results for two recently studied variants of <jats:sc>Matching Cut<\/jats:sc>, on <jats:italic>H<\/jats:italic>-free graphs. The first variant requires that the matching cut must be extendable to a perfect matching of the graph. The second variant requires the matching cut to be a perfect matching. In particular, we prove that there exists a small constant\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$r&gt;0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that the first variant is -complete for <jats:inline-formula><jats:alternatives><jats:tex-math>$$P_r$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>P<\/mml:mi>\n                    <mml:mi>r<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-free graphs. This addresses a question of Bouquet and Picouleau (The complexity of the Perfect Matching-Cut problem. CoRR, <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"http:\/\/arxiv.org\/abs\/2011.03318\">arXiv:2011.03318<\/jats:ext-link>, (2020)). For all three problems, we give state-of-the-art summaries of their computational complexity for <jats:italic>H<\/jats:italic>-free graphs.<\/jats:p>","DOI":"10.1007\/s00453-023-01137-9","type":"journal-article","created":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T14:02:28Z","timestamp":1686146548000},"page":"3290-3322","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Finding Matching Cuts in H-Free Graphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9860-2928","authenticated-orcid":false,"given":"Felicia","family":"Lucke","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5945-9287","authenticated-orcid":false,"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4395-5547","authenticated-orcid":false,"given":"Bernard","family":"Ries","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,6,7]]},"reference":[{"key":"1137_CR1","doi-asserted-by":"publisher","first-page":"2502","DOI":"10.1016\/j.dam.2011.07.021","volume":"160","author":"J Ara\u00fajo","year":"2012","unstructured":"Ara\u00fajo, J., Cohen, N., Giroire, F., Havet, F.: Good edge-labelling of graphs. Discrete Appl. Math. 160, 2502\u20132513 (2012)","journal-title":"Discrete Appl. Math."},{"key":"1137_CR2","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/j.dam.2021.05.016","volume":"319","author":"NR Aravind","year":"2022","unstructured":"Aravind, N.R., Kalyanasundaram, S., Kare, A.S.: Vertex partitioning problems on graphs with bounded tree width. Discrete Appl. Math. 319, 254\u2013270 (2022)","journal-title":"Discrete Appl. Math."},{"key":"1137_CR3","doi-asserted-by":"crossref","unstructured":"Aravind, N.R., Saxena, R.: An FPT algorithm for Matching Cut and $$d$$-Cut. Proc. IWOCA 2021, LNCS 12757, 531\u2013543 (2021)","DOI":"10.1007\/978-3-030-79987-8_37"},{"key":"1137_CR4","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1002\/jgt.20390","volume":"62","author":"PS Bonsma","year":"2009","unstructured":"Bonsma, P.S.: The complexity of the Matching-Cut problem for planar graphs and other graph classes. J. Graph Theory 62, 109\u2013126 (2009)","journal-title":"J. Graph Theory"},{"key":"1137_CR5","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1016\/j.tcs.2008.07.002","volume":"407","author":"M Borowiecki","year":"2008","unstructured":"Borowiecki, M., Jesse-J\u00f3zefczyk, K.: Matching cutsets in graphs of diameter $$2$$. Theor. Comput. Sci. 407, 574\u2013582 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"1137_CR6","unstructured":"Bouquet, V., Picouleau, C.: The complexity of the Perfect Matching-Cut problem. CoRR, arXiv:2011.03318, (2020)"},{"key":"1137_CR7","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00453-015-9989-6","volume":"75","author":"E Camby","year":"2016","unstructured":"Camby, E., Schaudt, O.: A new characterization of $${P}_k$$-free graphs. Algorithmica 75, 205\u2013217 (2016)","journal-title":"Algorithmica"},{"key":"1137_CR8","doi-asserted-by":"publisher","first-page":"1238","DOI":"10.1007\/s00453-020-00782-8","volume":"83","author":"C-Y Chen","year":"2021","unstructured":"Chen, C.-Y., Hsieh, S.-Y., Le, H.-O., Van Le, B., Peng, S.-L.: Matching Cut in graphs with large minimum degree. Algorithmica 83, 1238\u20131255 (2021)","journal-title":"Algorithmica"},{"key":"1137_CR9","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1016\/j.jctb.2011.07.002","volume":"102","author":"M Chudnovsky","year":"2012","unstructured":"Chudnovsky, M.: The structure of bull-free graphs II and III\u2014A summary. J. Comb. Theory Series B 102, 252\u2013282 (2012)","journal-title":"J. Comb. Theory Series B"},{"key":"1137_CR10","doi-asserted-by":"crossref","unstructured":"Chudnovsky, M., Seymour, P.: The structure of claw-free graphs. Surveys in Combinatorics, London Mathematical Society Lecture Note Series 327, 153\u2013171 (2005)","DOI":"10.1017\/CBO9780511734885.008"},{"key":"1137_CR11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1002\/jgt.3190080106","volume":"8","author":"V Chv\u00e1tal","year":"1984","unstructured":"Chv\u00e1tal, V.: Recognizing decomposable graphs. J. Graph Theory 8, 51\u201353 (1984)","journal-title":"J. Graph Theory"},{"key":"1137_CR12","doi-asserted-by":"crossref","unstructured":"Dabrowski, K.K., Johnson, M., Paulusma, D.: Clique-width for hereditary graph classes. Proc. BCC 2019, London Mathematical Society Lecture Note Series 456, 1\u201356 (2019)","DOI":"10.1017\/9781108649094.002"},{"key":"1137_CR13","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1006\/jctb.2001.2079","volume":"84","author":"AA Diwan","year":"2002","unstructured":"Diwan, A.A.: Disconnected 2-factors in planar cubic bridgeless graphs. J. Comb. Theory Series B 84, 249\u2013259 (2002)","journal-title":"J. Comb. Theory Series B"},{"key":"1137_CR14","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1002\/net.3230120404","volume":"12","author":"AM Farley","year":"1982","unstructured":"Farley, A.M., Proskurowski, A.: Networks immune to isolated line failures. Networks 12, 393\u2013403 (1982)","journal-title":"Networks"},{"key":"1137_CR15","doi-asserted-by":"publisher","first-page":"106294","DOI":"10.1016\/j.ipl.2022.106294","volume":"179","author":"C Feghali","year":"2023","unstructured":"Feghali, C.: A note on Matching-Cut in $${P}_t$$-free graphs. Inf. Process. Lett. 179, 106294 (2023)","journal-title":"Inf. Process. Lett."},{"key":"1137_CR16","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/S0095-8956(02)00031-X","volume":"87","author":"M Funk","year":"2003","unstructured":"Funk, M., Jackson, B., Labbate, D., Sheehan, J.: $$2$$-Factor hamiltonian graphs. J. Comb. Theory Series B 87, 138\u2013144 (2003)","journal-title":"J. Comb. Theory Series B"},{"key":"1137_CR17","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/jgt.22028","volume":"84","author":"PA Golovach","year":"2017","unstructured":"Golovach, P.A., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of colouring graphs with forbidden subgraphs. J. Graph Theory 84, 331\u2013363 (2017)","journal-title":"J. Graph Theory"},{"key":"1137_CR18","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.jcss.2021.07.005","volume":"123","author":"PA Golovach","year":"2022","unstructured":"Golovach, P.A., Komusiewicz, C., Kratsch, D., Van Le, B.: Refined notions of parameterized enumeration kernels with applications to matching cut enumeration. J. Comput. Syst. Sci. 123, 76\u2013102 (2022)","journal-title":"J. Comput. Syst. Sci."},{"key":"1137_CR19","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2012.06.039","volume":"457","author":"PA Golovach","year":"2012","unstructured":"Golovach, P.A., Paulusma, D., Song, J.: Computing vertex-surjective homomorphisms to partially reflexive trees. Theor. Comput. Sci. 457, 86\u2013100 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"1137_CR20","doi-asserted-by":"publisher","first-page":"1677","DOI":"10.1007\/s00453-021-00798-8","volume":"83","author":"G Gomes","year":"2021","unstructured":"Gomes, G., Sau, I.: Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization. Algorithmica 83, 1677\u20131706 (2021)","journal-title":"Algorithmica"},{"key":"1137_CR21","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1111\/j.1749-6632.1970.tb56468.x","volume":"175","author":"RL Graham","year":"1970","unstructured":"Graham, R.L.: On primitive graphs and optimal vertex assignments. Ann. New York Acad. Sci. 175, 170\u2013186 (1970)","journal-title":"Ann. New York Acad. Sci."},{"key":"1137_CR22","first-page":"128","volume":"5","author":"P Heggernes","year":"1998","unstructured":"Heggernes, P., Telle, J.A.: Partitioning graphs into generalized dominating sets. Nord. J. Comput. 5, 128\u2013142 (1998)","journal-title":"Nord. J. Comput."},{"key":"1137_CR23","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/3301445","volume":"15","author":"D Hermelin","year":"2019","unstructured":"Hermelin, D., Mnich, M., van Leeuwen, E.J., Woeginger, G.J.: Domination when the stars are out. ACM Trans. Algorithms 15, 25:1-25:90 (2019)","journal-title":"ACM Trans. Algorithms"},{"key":"1137_CR24","unstructured":"Kern, W., Paulusma, D.: Contracting to a longest path in $${H}$$-free graphs. Proc. ISAAC 2020, LIPIcs 181, 22:1\u201322:18 (2020)"},{"key":"1137_CR25","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.dam.2019.12.010","volume":"283","author":"C Komusiewicz","year":"2020","unstructured":"Komusiewicz, C., Kratsch, D., Van Le, B.: Matching Cut: kernelization, single-exponential time FPT, and exact exponential algorithms. Discrete Appl. Math. 283, 44\u201358 (2020)","journal-title":"Discrete Appl. Math."},{"key":"1137_CR26","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1016\/j.tcs.2015.10.016","volume":"609","author":"D Kratsch","year":"2016","unstructured":"Kratsch, D., Van Le, B.: Algorithms solving the Matching Cut problem. Theor. Comput. Sci. 609, 328\u2013335 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"1137_CR27","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.tcs.2018.10.029","volume":"770","author":"H Le","year":"2019","unstructured":"Le, H., Van Le, B.: A complexity dichotomy for Matching Cut in (bipartite) graphs of fixed diameter. Theor. Comput. Sci. 770, 69\u201378 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"1137_CR28","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1016\/S0304-3975(03)00048-3","volume":"301","author":"VB Le","year":"2003","unstructured":"Le, V.B., Randerath, B.: On stable cutsets in line graphs. Theor. Comput. Sci. 301, 463\u2013475 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"1137_CR29","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.tcs.2022.07.035","volume":"931","author":"VB Le","year":"2022","unstructured":"Le, V.B., Telle, J.A.: The perfect Matching Cut problem revisited. Theor. Comput. Sci. 931, 117\u2013130 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"1137_CR30","unstructured":"Lucke, F., Paulusma, D., Ries, B.: Finding Matching Cuts in $$H$$-free graphs. Proc. ISAAC 2022, LIPIcs 248, 22:1\u201322:16 (2022)"},{"key":"1137_CR31","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.tcs.2022.09.014","volume":"936","author":"F Lucke","year":"2022","unstructured":"Lucke, F., Paulusma, D., Ries, B.: On the complexity of Matching Cut for graphs of bounded radius and $${H}$$-free graphs. Theor. Comput. Sci. 936, 33\u201342 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"1137_CR32","doi-asserted-by":"publisher","first-page":"106213","DOI":"10.1016\/j.ipl.2021.106213","volume":"174","author":"B Martin","year":"2022","unstructured":"Martin, B., Paulusma, D., Smith, S.: Hard problems that quickly become very easy. Inf. Process. Lett. 174, 106213 (2022)","journal-title":"Inf. Process. Lett."},{"key":"1137_CR33","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1002\/jgt.3190130502","volume":"13","author":"AM Moshi","year":"1989","unstructured":"Moshi, A.M.: Matching Cutsets in graphs. J. Graph Theory 13, 527\u2013536 (1989)","journal-title":"J. Graph Theory"},{"key":"1137_CR34","doi-asserted-by":"crossref","unstructured":"Patrignani, M., Pizzonia, M.: The complexity of the Matching\u2013Cut problem. Proc. WG 2001, LNCS 2204, 284\u2013295 (2001)","DOI":"10.1007\/3-540-45477-2_26"},{"key":"1137_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-003-0540-1","volume":"20","author":"B Randerath","year":"2004","unstructured":"Randerath, B., Schiermeyer, I.: Vertex colouring and forbidden subgraphs\u2014A survey. Graphs Comb. 20, 1\u201340 (2004)","journal-title":"Graphs Comb."},{"key":"1137_CR36","unstructured":"Schmidt, T.: Computational complexity of SAT, XSAT and NAE-SAT for linear and mixed Horn CNF formulas. PhD thesis, Universit\u00e4t zu K\u00f6ln, (2010)"},{"key":"1137_CR37","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1016\/j.dam.2008.08.025","volume":"158","author":"P Van \u2019t Hof","year":"2010","unstructured":"Van \u2019t Hof, P.: A new characterization of $${P}_6$$-free graphs. Discrete Appl. Math. 158, 731\u2013740 (2010)","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01137-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01137-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01137-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T14:08:24Z","timestamp":1695737304000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01137-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,7]]},"references-count":37,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["1137"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01137-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,7]]},"assertion":[{"value":"9 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2023","order":3,"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 no competing interests as defined by Springer, or other interests that might be perceived to influence the results and\/or discussion reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of intetrest"}}]}}