Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius

Lucke, Felicia; Paulusma, Daniël; Ries, Bernard

Abstract

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.

Citation

Lucke, F., Paulusma, D., & Ries, B. (2023, August). Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
• Start Date: Aug 28, 2023
• End Date: Sep 1, 2023
• Acceptance Date: Jul 18, 2023
• Online Publication Date: Aug 21, 2023
• Publication Date: Aug 21, 2023
• Deposit Date: Dec 29, 2023
• Publicly Available Date: Jan 2, 2024
• Volume: 272
• Pages: 64:1-64:15
• Series Title: Leibniz International Proceedings in Informatics (LIPIcs)
• Book Title: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
• DOI: https://doi.org/10.4230/LIPIcs.MFCS.2023.64
• Keywords: and phrases matching cut; perfect matching; H-free graph; diameter; radius; dichotomy
• Public URL: https://durham-repository.worktribe.com/output/2063716