{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:50:20Z","timestamp":1780822220104,"version":"3.54.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T00:00:00Z","timestamp":1606089600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T00:00:00Z","timestamp":1606089600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100012688","name":"Universit\u00e4t Rostock","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012688","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,5]]},"abstract":"Abstract<\/jats:title>In a graph, a matching cut is an edge cut that is a matching. Matching<\/jats:sc> Cut<\/jats:sc> is the problem of deciding whether or not a given graph has a matching cut, which is known to be $${\\mathsf {NP}}$$<\/jats:tex-math>\n NP<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete. While Matching<\/jats:sc> Cut<\/jats:sc> is trivial for graphs with minimum degree at most one, it is $${\\mathsf {NP}}$$<\/jats:tex-math>\n NP<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete on graphs with minimum degree two. In this paper, we show that, for any given constant $$c>1$$<\/jats:tex-math>\n \n c<\/mml:mi>\n ><\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, Matching<\/jats:sc> Cut<\/jats:sc> is $${\\mathsf {NP}}$$<\/jats:tex-math>\n NP<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete in the class of graphs with minimum degree c<\/jats:italic> and this restriction of Matching<\/jats:sc> Cut<\/jats:sc> has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant $$\\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>, Matching<\/jats:sc> Cut<\/jats:sc> remains $${\\mathsf {NP}}$$<\/jats:tex-math>\n NP<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete in the class of n<\/jats:italic>-vertex (bipartite) graphs with unbounded minimum degree $$\\delta >n^{1-\\epsilon }$$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n ><\/mml:mo>\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:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We give an exact branching algorithm to solve Matching<\/jats:sc> Cut<\/jats:sc> for graphs with minimum degree $$\\delta \\ge 3$$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n \u2265<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in $$O^*(\\lambda ^n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n \n (<\/mml:mo>\n \n \u03bb<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, where $$\\lambda$$<\/jats:tex-math>\n \u03bb<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the positive root of the polynomial $$x^{\\delta +1}-x^{\\delta }-1$$<\/jats:tex-math>\n \n \n x<\/mml:mi>\n \n \u03b4<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n -<\/mml:mo>\n \n x<\/mml:mi>\n \u03b4<\/mml:mi>\n <\/mml:msup>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Despite the hardness results, this is a very fast exact exponential-time algorithm for Matching<\/jats:sc> Cut<\/jats:sc> on graphs with large minimum degree; for instance, the running time is $$O^*(1.0099^n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n .<\/mml:mo>\n \n 0099<\/mml:mn>\n n<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> on graphs with minimum degree $$\\delta \\ge 469$$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n \u2265<\/mml:mo>\n 469<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Complementing our hardness results, we show that, for any two fixed constants $$1< c <4$$<\/jats:tex-math>\n \n 1<\/mml:mn>\n <<\/mml:mo>\n c<\/mml:mi>\n <<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$c^{\\prime }\\ge 0$$<\/jats:tex-math>\n \n \n c<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n \u2265<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, Matching<\/jats:sc> Cut<\/jats:sc> is solvable in polynomial time for graphs with large minimum degree $$\\delta \\ge \\frac{1}{c}n-c^{\\prime }$$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n \u2265<\/mml:mo>\n \n 1<\/mml:mn>\n c<\/mml:mi>\n <\/mml:mfrac>\n n<\/mml:mi>\n -<\/mml:mo>\n \n c<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00453-020-00782-8","type":"journal-article","created":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T15:37:53Z","timestamp":1606145873000},"page":"1238-1255","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Matching Cut in Graphs with Large Minimum Degree"],"prefix":"10.1007","volume":"83","author":[{"given":"Chi-Yeh","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sun-Yuan","family":"Hsieh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hoang-Oanh","family":"Le","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3303-8326","authenticated-orcid":false,"given":"Van Bang","family":"Le","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sheng-Lung","family":"Peng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,11,23]]},"reference":[{"issue":"18","key":"782_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(18), 2502\u20132513 (2012). https:\/\/doi.org\/10.1016\/j.dam.2011.07.021","journal-title":"Discrete Appl. Math."},{"key":"782_CR2","doi-asserted-by":"publisher","unstructured":"Aravind, N.R., Kalyanasundaram, S., Kare, A.S.: On structural parameterizations of the matching cut problem. In: Combinatorial Optimization and Applications\u201411th International Conference, COCOA 2017, Shanghai, China, 16\u201318 December 2017, Proceedings, Part II, pp. 475\u2013482 (2017). https:\/\/doi.org\/10.1007\/978-3-319-71147-8_34","DOI":"10.1007\/978-3-319-71147-8_34"},{"issue":"2","key":"782_CR3","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(2), 109\u2013126 (2009). https:\/\/doi.org\/10.1002\/jgt.20390","journal-title":"J. Graph Theory"},{"issue":"1\u20133","key":"782_CR4","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(1\u20133), 574\u2013582 (2008). https:\/\/doi.org\/10.1016\/j.tcs.2008.07.002","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"782_CR5","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(1), 51\u201353 (1984). https:\/\/doi.org\/10.1002\/jgt.3190080106","journal-title":"J. Graph Theory"},{"issue":"4","key":"782_CR6","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(4), 393\u2013403 (1982). https:\/\/doi.org\/10.1002\/net.3230120404","journal-title":"Networks"},{"key":"782_CR7","volume-title":"Fomin and Dieter Kratsch. Exact Exponential Algorithms","author":"V Fedor","year":"2010","unstructured":"Fedor, V.: Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer, Berlin (2010)"},{"key":"782_CR8","doi-asserted-by":"publisher","unstructured":"Gomes, G.C.M., Sau, I.: Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization. In: 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, 11\u201313 September 2019, Munich, Germany, pp. 19:1\u201319:15 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2019.19","DOI":"10.4230\/LIPIcs.IPEC.2019.19"},{"issue":"1","key":"782_CR9","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(1), 170\u2013186 (1970)","journal-title":"Ann. N. Y. Acad. Sci."},{"key":"782_CR10","doi-asserted-by":"publisher","unstructured":"Hsieh, S.-Y., Le, H.-O., Le, V.B., Peng, S.-L.: Matching cut in graphs with large minimum degree. In: Computing and Combinatorics\u201425th International Conference, COCOON 2019, Xi\u2019an, China, 29\u201331 July 2019, Proceedings, pp. 301\u2013312 (2019). https:\/\/doi.org\/10.1007\/978-3-030-26176-4_25","DOI":"10.1007\/978-3-030-26176-4_25"},{"issue":"2","key":"782_CR11","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-sat. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"782_CR12","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"key":"782_CR13","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. Discrete Appl. Math. 283, 44\u201358 (2020). https:\/\/doi.org\/10.1016\/j.dam.2019.12.010","journal-title":"Discrete Appl. Math."},{"key":"782_CR14","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. Theor. Comput. Sci. 609, 328\u2013335 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2015.10.016","journal-title":"Theor. Comput. Sci."},{"key":"782_CR15","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. Theor. Comput. Sci. 770, 69\u201378 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2018.10.029","journal-title":"Theor. Comput. Sci."},{"issue":"301","key":"782_CR16","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1016\/S0304-3975(03)00048-3","volume":"1\u20133","author":"VB Le","year":"2003","unstructured":"Le, V.B., Randerath, B.: On stable cutsets in line graphs. Theor. Comput. Sci. 1\u20133(301), 463\u2013475 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(03)00048-3","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"782_CR17","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(5), 527\u2013536 (1989). https:\/\/doi.org\/10.1002\/jgt.3190130502","journal-title":"J. Graph Theory"},{"key":"782_CR18","doi-asserted-by":"publisher","unstructured":"Patrignani, M., Pizzonia, M.: The complexity of the matching-cut problem. In: Graph-Theoretic Concepts in Computer Science, 27th International Workshop, WG 2001, Boltenhagen, Germany, 14\u201316 June 2001, Proceedings, pp. 284\u2013295 (2001). https:\/\/doi.org\/10.1007\/3-540-45477-2_26","DOI":"10.1007\/3-540-45477-2_26"},{"issue":"1\u20133","key":"782_CR19","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0012-365X(01)00173-X","volume":"247","author":"I Rusu","year":"2002","unstructured":"Rusu, I., Spinrad, J.P.: Forbidden subgraph decomposition. Discrete Math. 247(1\u20133), 159\u2013168 (2002). https:\/\/doi.org\/10.1016\/S0012-365X(01)00173-X","journal-title":"Discrete Math."},{"issue":"4","key":"782_CR20","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1007\/s00224-012-9412-5","volume":"52","author":"JMM van Rooij","year":"2013","unstructured":"van Rooij, J.M.M., van Kooten Niekerk, M.E., Bodlaender, H.L.: Partition into triangles on bounded degree graphs. Theory Comput. Syst. 52(4), 687\u2013718 (2013). https:\/\/doi.org\/10.1007\/s00224-012-9412-5","journal-title":"Theory Comput. Syst."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00782-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00782-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00782-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T10:20:28Z","timestamp":1617877228000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00782-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,23]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["782"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00782-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,23]]},"assertion":[{"value":"14 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}