{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:52Z","timestamp":1770994132803,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T00:00:00Z","timestamp":1613606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T00:00:00Z","timestamp":1613606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["Finance Code 001"],"award-info":[{"award-number":["Finance Code 001"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Agence nationale de la recherche","award":["ANR-16-CE40-0028"],"award-info":[{"award-number":["ANR-16-CE40-0028"]}]},{"name":"Agence nationale de la recherche","award":["ANR-17\u2013CE23-0010"],"award-info":[{"award-number":["ANR-17\u2013CE23-0010"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00453-021-00798-8","type":"journal-article","created":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T06:57:56Z","timestamp":1613717876000},"page":"1677-1706","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5164-1460","authenticated-orcid":false,"given":"Guilherme C. M.","family":"Gomes","sequence":"first","affiliation":[]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,18]]},"reference":[{"key":"798_CR1","doi-asserted-by":"crossref","unstructured":"Aravind, N.R., Kalyanasundaram, S., Kare, A.S.: On structural parameterizations of the matching cut problem. In: Proceedings of the 11th International Conference on Combinatorial Optimization and Applications (COCOA), Vol. 10628 of LNCS, pp. 475\u2013482 (2017)","DOI":"10.1007\/978-3-319-71147-8_34"},{"issue":"1","key":"798_CR2","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/jgt.21909","volume":"83","author":"A Ban","year":"2016","unstructured":"Ban, A., Linial, N.: Internal partitions of regular graphs. J. Graph Theory 83(1), 5\u201318 (2016)","journal-title":"J. Graph Theory"},{"issue":"8","key":"798_CR3","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"798_CR4","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: A new technique for kernelization lower bounds. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), Vol.\u00a09 of LIPIcs, pp. 165\u2013176 (2011)"},{"issue":"2","key":"798_CR5","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)","journal-title":"J. Graph Theory"},{"issue":"2","key":"798_CR6","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00224-015-9631-7","volume":"58","author":"A Boral","year":"2016","unstructured":"Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: A fast branching algorithm for cluster vertex deletion. Theory Comput. Syst. 58(2), 357\u2013376 (2016)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"798_CR7","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)","journal-title":"J. Graph Theory"},{"issue":"1","key":"798_CR8","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"798_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"798_CR10","unstructured":"DeVos, M.: http:\/\/www.openproblemgarden.org\/op\/friendly\\_partitions (2009)"},{"key":"798_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory, vol. 173, 4th edn. Springer, Berlin (2010)","edition":"4"},{"key":"798_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"key":"798_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Berlin (2010)"},{"key":"798_CR14","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019)"},{"issue":"1","key":"798_CR15","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"798_CR16","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(1), 170\u2013186 (1970)","journal-title":"Ann. New York Acad. Sci."},{"issue":"2","key":"798_CR17","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)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"798_CR18","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1002\/(SICI)1097-0118(199801)27:1<7::AID-JGT2>3.0.CO;2-U","volume":"27","author":"A Kaneko","year":"1998","unstructured":"Kaneko, A.: On decomposition of triangle-free graphs under degree constraints. J. Graph Theory 27(1), 7\u20139 (1998)","journal-title":"J. Graph Theory"},{"key":"798_CR19","volume-title":"Treewidth. Computations and Approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. Computations and Approximations. Springer, Berlin (1994)"},{"key":"798_CR20","doi-asserted-by":"crossref","unstructured":"Komusiewicz, C., Kratsch, D., Le, V.B.: Matching cut: Kernelization, single-exponential time fpt, and exact exponential algorithms. 283, 44\u201358 (2020)","DOI":"10.1016\/j.dam.2019.12.010"},{"key":"798_CR21","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. Theo. Comput. Sci. 609, 328\u2013335 (2016)","journal-title":"Theo. Comput. Sci."},{"key":"798_CR22","unstructured":"Le, H., Le, V.B.: On the complexity of matching cut in graphs of fixed diameter. In: Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC), Vol.\u00a064 of LIPIcs, pp. 50:1\u201350:12 (2016)"},{"issue":"1\u20133","key":"798_CR23","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. Theo. Comput. Sci. 301(1\u20133), 463\u2013475 (2003)","journal-title":"Theo. Comput. Sci."},{"key":"798_CR24","unstructured":"Lov\u00e1sz, L.: Coverings and colorings of hypergraphs. In: Proceedings of the 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing, pp. 3\u201312. Utilitas Mathematica Publishing (1973)"},{"issue":"1","key":"798_CR25","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1002\/jgt.22364","volume":"90","author":"J Ma","year":"2019","unstructured":"Ma, J., Yang, T.: Decomposing $$C_4$$-free graphs under degree constraints. J. Graph Theory 90(1), 13\u201323 (2019)","journal-title":"J. Graph Theory"},{"key":"798_CR26","doi-asserted-by":"crossref","unstructured":"Marx, D., O\u2019sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms, 9(4) (2013)","DOI":"10.1145\/2500119"},{"issue":"5","key":"798_CR27","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)","journal-title":"J. Graph Theory"},{"key":"798_CR28","doi-asserted-by":"crossref","unstructured":"M.\u00a0Patrignani, M., Pizzonia, M.: The complexity of the matching-cut problem. In: Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Vol. 2204 of LNCS, pp. 284\u2013295 (2001)","DOI":"10.1007\/3-540-45477-2_26"},{"issue":"3","key":"798_CR29","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"798_CR30","unstructured":"K.\u00a0H. Shafique, K. H., Dutton, R.\u00a0D.: On satisfactory partitioning of graphs. Congressus Numerantium, pp 183\u2013194, (2002)"},{"issue":"3","key":"798_CR31","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1002\/(SICI)1097-0118(199611)23:3<321::AID-JGT12>3.0.CO;2-H","volume":"23","author":"M Stiebitz","year":"1996","unstructured":"Stiebitz, M.: Decomposing graphs under degree constraints. J. Graph Theory 23(3), 321\u2013324 (1996)","journal-title":"J. Graph Theory"},{"issue":"2","key":"798_CR32","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1002\/jgt.3190070204","volume":"7","author":"C Thomassen","year":"1983","unstructured":"Thomassen, C.: Graph decomposition with constraints on the connectivity and minimum degree. J. Graph Theory 7(2), 165\u2013167 (1983)","journal-title":"J. Graph Theory"},{"key":"798_CR33","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C Yap","year":"1983","unstructured":"Yap, C.: Some consequences of non-uniform conditions on uniform classes. Theo. Comput. Sci. 26, 287\u2013300 (1983)","journal-title":"Theo. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00798-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00798-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00798-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T10:05:56Z","timestamp":1621937156000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00798-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,18]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["798"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00798-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,18]]},"assertion":[{"value":"28 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}