2026-07-22T12:37:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18598 2024-03-06T11:02:13Z ddc:004 open_access

Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius Lucke, Felicia Paulusma, Daniël Ries, Bernard matching cut perfect matching H-free graph diameter radius dichotomy The (Perfect) Matching Cut problem is to decide if a graph G has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of G. Both Matching Cut and Perfect Matching Cut are known to be NP-complete, leading to many complexity results for both problems on special graph classes. A perfect matching cut is also a matching cut with maximum number of edges. To increase our understanding of the relationship between the two problems, we introduce the Maximum Matching Cut problem. This problem is to determine a largest matching cut in a graph. We generalize and unify known polynomial-time algorithms for Matching Cut and Perfect Matching Cut restricted to graphs of diameter at most 2 and to (P₆+sP₂)-free graphs. We also show that the complexity of Maximum Matching Cut differs from the complexities of Matching Cut and Perfect Matching Cut by proving NP-hardness of Maximum Matching Cut for 2P₃-free quadrangulated graphs of diameter 3 and radius 2 and for subcubic line graphs of triangle-free graphs. In this way, we obtain full dichotomies of Maximum Matching Cut for graphs of bounded diameter, bounded radius and H-free graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Felicia Lucke and Daniël Paulusma and Bernard Ries 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.64 urn:nbn:de:0030-drops-185981 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.64 eng https://creativecommons.org/licenses/by/4.0/legalcode