Dichotomies for Maximum Matching Cut: H-freeness, bounded diameter, bounded radius
Felicia Lucke, Daniรซl Paulusma, Bernard Ries ยท Theoretical Computer Science ยท 2024
Matching cut Perfect matching ๐ป-free graph Diameter Radius DichotomyThe (Perfect) Matching Cut problem is to decide if a graph ๐บ has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of ๐บ.Both Matching Cut and Perfect Matching Cut are known to be NP-complete.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 perform a complexity study for the Maximum Matching Cut problem, which is to determine a largest matching cut in a graph.Our results yield full dichotomies of Maximum Matching Cut for graphs of bounded diameter, bounded radius and ๐ป-free graphs.A disconnected perfect matching of a graph ๐บ is a perfect matching that contains a matching cut of ๐บ.We also show how our new techniques can be used for finding a disconnected perfect matching with a largest matching cut for special graph classes.In this way we can prove that the decision problem Disconnected Perfect Matching is polynomial-time solvable for (๐ 6 + ๐ ๐ 2 )-free graphs for every ๐ โฅ 0, extending a known result for ๐ 5 -free graphs (Bouquet and Picouleau, 2020).