{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,14]],"date-time":"2026-09-14T01:09:10Z","timestamp":1789348150445,"version":"build-2803163510"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T00:00:00Z","timestamp":1746662400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T00:00:00Z","timestamp":1746662400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005869","name":"University of Fribourg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005869","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The <jats:sc>(Perfect) Matching Cut<\/jats:sc> problem is to decide if a connected graph has a (perfect) matching that is also an edge cut. The <jats:sc>Disconnected Perfect Matching<\/jats:sc> problem is to decide if a connected graph has a perfect matching that contains a matching cut. Both <jats:sc>Matching Cut<\/jats:sc> and <jats:sc>Disconnected Perfect Matching<\/jats:sc> are -complete for planar graphs of girth\u00a05, whereas <jats:sc>Perfect Matching Cut<\/jats:sc> is known to be -complete even for subcubic bipartite graphs of arbitrarily large fixed girth. We prove that <jats:sc>Matching Cut<\/jats:sc> and <jats:sc>Disconnected Perfect Matching<\/jats:sc> are also -complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Our result for <jats:sc>Matching Cut<\/jats:sc> resolves a 20-year old open problem. We also show that the more general problem  <jats:italic>d<\/jats:italic>\n            <jats:sc>-Cut<\/jats:sc>, for every fixed <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$d\\ge 1$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>d<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, is -complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Furthermore, we show that <jats:sc>Matching Cut<\/jats:sc>, <jats:sc>Perfect Matching Cut<\/jats:sc> and <jats:sc>Disconnected Perfect Matching<\/jats:sc> are -complete for <jats:italic>H<\/jats:italic>-free graphs whenever <jats:italic>H<\/jats:italic> contains a connected component with two vertices of degree at least\u00a03. Afterwards, we update the state-of-the-art summaries for <jats:italic>H<\/jats:italic>-free graphs and compare them with each other, and with a known and full classification of the <jats:sc>Maximum Matching Cut<\/jats:sc> problem, which is to determine a largest matching cut of a graph\u00a0<jats:italic>G<\/jats:italic>. Finally, by combining existing results, we obtain a complete complexity classification of <jats:sc>Perfect Matching Cut<\/jats:sc> for <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathcal{H}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>H<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-subgraph-free graphs where <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathcal{H}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>H<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> is any finite set of graphs.<\/jats:p>","DOI":"10.1007\/s00453-025-01318-8","type":"journal-article","created":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T10:48:41Z","timestamp":1746701321000},"page":"1199-1221","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Matching Cuts in Graphs of High Girth and H-Free Graphs"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6727-7213","authenticated-orcid":false,"given":"Carl","family":"Feghali","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9860-2928","authenticated-orcid":false,"given":"Felicia","family":"Lucke","sequence":"additional","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":[[2025,5,8]]},"reference":[{"key":"1318_CR1","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0095-8956(85)90092-9","volume":"38","author":"N Alon","year":"1985","unstructured":"Alon, N., Milman, V.D.: $$\\lambda $$1, isoperimetric inequalities for graphs, and superconcentrators. J. Comb. Theory Ser. B 38, 73\u201388 (1985)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1318_CR2","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. Discret. Appl. Math. 160, 2502\u20132513 (2012)","journal-title":"Discret. Appl. Math."},{"key":"1318_CR3","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. Discret. Appl. Math. 319, 254\u2013270 (2022)","journal-title":"Discret. Appl. Math."},{"key":"1318_CR4","doi-asserted-by":"crossref","unstructured":"Aravind, N.R., Saxena, R.: An FPT algorithm for Matching Cut and $$d$$-Cut. In: Proc. IWOCA 2021, LNCS, vol. 12757, pp. 531\u2013543. (2021)","DOI":"10.1007\/978-3-030-79987-8_37"},{"key":"1318_CR5","doi-asserted-by":"crossref","unstructured":"Bonnet, E., Chakraborty, D., Duron, J.: Cutting barnette graphs perfectly is hard. In: Proc. WG 2023, LNCS, to appear","DOI":"10.1007\/978-3-031-43380-1_9"},{"key":"1318_CR6","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). ((conference version: WG 2003))","journal-title":"J. Graph Theory"},{"key":"1318_CR7","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$$. Theoret. Comput. Sci. 407, 574\u2013582 (2008)","journal-title":"Theoret. Comput. Sci."},{"key":"1318_CR8","unstructured":"Bouquet, V., Picouleau, C.: The complexity of the Perfect Matching-Cut problem. arxiv:2011.03318 (2020)"},{"key":"1318_CR9","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., Le, V.B., Peng, S.-L.: Matching cut in graphs with large minimum degree. Algorithmica 83, 1238\u20131255 (2021)","journal-title":"Algorithmica"},{"key":"1318_CR10","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":"1318_CR11","unstructured":"Dirichlet, P.L.: Beweis des Satzes, dass jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Faktor sind, unendlich viele Primzahlen enth\u00e4lt. Abhandlungen der K\u00f6niglichen Preu\u00dfischen Akademie der Wissenschaften zu Berlin, (1837)"},{"key":"1318_CR12","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1090\/S0002-9947-1984-0743744-X","volume":"284","author":"J Dodziuk","year":"1984","unstructured":"Dodziuk, J.: Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Am. Math. Soc. 284, 787\u2013794 (1984)","journal-title":"Trans. Am. Math. Soc."},{"key":"1318_CR13","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":"1318_CR14","doi-asserted-by":"publisher","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":"1318_CR15","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., Le, V.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":"1318_CR16","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. Theoret. Comput. Sci. 457, 86\u2013100 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"1318_CR17","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":"1318_CR18","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. N. Y. Acad. Sci. 175, 170\u2013186 (1970)","journal-title":"Ann. N. Y. Acad. Sci."},{"key":"1318_CR19","first-page":"128","volume":"5","author":"P Heggernes","year":"1998","unstructured":"Heggernes, P., Telle, J.A.: Partitioning graphs into generalized dominating sets. Nordic J. Comput. 5, 128\u2013142 (1998)","journal-title":"Nordic J. Comput."},{"key":"1318_CR20","unstructured":"Johnson, M., Martin, B., Oostveen, J.J., Pandey, S., Paulusma, D., Smith, S., van Leeuwen, E.J.: Complexity framework for forbidden subgraphs I: The framework. arxiv:2211.12887 (2022)"},{"key":"1318_CR21","unstructured":"Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S. and Van Leeuwen, E.J.: Complexity framework for forbidden subgraphs III: When problems are tractable on subcubic graphs. In: Proc. MFCS 2023, LIPIcs, Vol 272, pp. 57:1\u201357. (2023)"},{"key":"1318_CR22","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., Le, V.B.: Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms. Discret. Appl. Math. 283, 44\u201358 (2020)","journal-title":"Discret. Appl. Math."},{"key":"1318_CR23","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., Le, V.B.: Algorithms solving the Matching Cut problem. Theoret. Comput. Sci. 609, 328\u2013335 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"1318_CR24","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.tcs.2018.10.029","volume":"770","author":"H-O Le","year":"2019","unstructured":"Le, H.-O., Le, V.B.: A complexity dichotomy for Matching Cut in (bipartite) graphs of fixed diameter. Theoret. Comput. Sci. 770, 69\u201378 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"1318_CR25","doi-asserted-by":"crossref","unstructured":"Le, H.-O., Le, V. B.: Complexity results for matching cut problems in graphs without long induced paths. In: Proc. WG, LNCS, to appear (2023)","DOI":"10.2139\/ssrn.4789852"},{"key":"1318_CR26","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. Theoret. Comput. Sci. 301, 463\u2013475 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"1318_CR27","first-page":"182","volume":"12911","author":"VB Le","year":"2021","unstructured":"Le, V.B., Telle, J.A.: The perfect matching cut problem revisited. Proc. WG 2021 LNCS 12911, 182\u2013194 (2021)","journal-title":"Proc. WG 2021 LNCS"},{"key":"1318_CR28","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A Lubotzky","year":"1988","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8, 261\u2013277 (1988)","journal-title":"Combinatorica"},{"key":"1318_CR29","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":"1318_CR30","first-page":"64:1","volume":"272","author":"F Lucke","year":"2023","unstructured":"Lucke, F., Paulusma, D., Ries, B.: Dichotomies for maximum matching cut: H-Freeness, bounded diameter, bounded radius. Proc. MFCS 2023, LIPIcs, 272, 64:1-64:15 (2023)","journal-title":"Proc. MFCS 2023, LIPIcs,"},{"key":"1318_CR31","unstructured":"Lucke, F., Paulusma, D., Ries, B.: Finding matching cuts in $${H}$$-free graphs. Algorithmica, to appear"},{"key":"1318_CR32","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":"1318_CR33","unstructured":"Open problem garden. http:\/\/www.openproblemgarden.org\/op\/matching_cut_and_girth. Accessed 22 June 2023"},{"key":"1318_CR34","first-page":"284","volume":"2204","author":"M Patrignani","year":"2001","unstructured":"Patrignani, M.: The complexity of the Matching-Cut problem. Proc. WG 2001 LNCS 2204, 284\u2013295 (2001)","journal-title":"Proc. WG 2001 LNCS"},{"key":"1318_CR35","volume-title":"Introduction to the Theory of Number","author":"HN Shapiro","year":"2008","unstructured":"Shapiro, H.N.: Introduction to the Theory of Number. Dover Publications, New York (2008)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01318-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01318-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01318-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T13:37:51Z","timestamp":1757165871000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01318-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,8]]},"references-count":35,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["1318"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01318-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,8]]},"assertion":[{"value":"29 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2025","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 Conflict of interest 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 interest"}}]}}