Dichotomies for Maximum Matching Cut: H-freeness, bounded diameter, bounded radius
BP2-STS
- Lucke, Felicia ORCID Université de Fribourg, Switzerland
- Paulusma, Daniël ORCID Durham University, United Kingdom
- Ries, Bernard ORCID Université de Fribourg, Switzerland
- 2024
Published in:
- Theoretical Computer Science. - Elsevier BV. - 2024, vol. 1017, p. 114795
English
The (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).
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- CC BY
- Open access status
- hybrid
- Identifiers
-
- DOI 10.1016/j.tcs.2024.114795
- ISSN 0304-3975
- Persistent URL
- https://folia.unifr.ch/unifr/documents/329174
Statistics
Document views: 13
File downloads:
- matchingcut.pdf: 20