Finding Matching Cuts in H-Free Graphs
BP2-STS
- Lucke, Felicia ORCID Université de Fribourg, Switzerland
- Paulusma, Daniël ORCID Durham University, United Kingdom
- Ries, Bernard ORCID Université de Fribourg, Switzerland
- 2023
Published in:
- Algorithmica. - Springer Science and Business Media LLC. - 2023, vol. 85, no. 10, p. 3290-3322
English
The well-known NP-complete problem Matching Cut is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for Matching Cut restricted to H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. We also prove new complexity results for two recently studied variants of Matching Cut, on H-free graphs. The first variant requires that the matching cut must be extendable to a perfect matching of the graph. The second variant requires the matching cut to be a perfect matching. In particular, we prove that there exists a small constant r > 0 such that the first variant is NPcomplete for Pr -free graphs. This addresses a question of Bouquet and Picouleau (The complexity of the Perfect Matching-Cut problem. CoRR, arXiv:2011.03318, (2020)). For all three problems, we give state-of-the-art summaries of their computational complexity for H-free graphs.
- 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.1007/s00453-023-01137-9
- ISSN 0178-4617
- Persistent URL
- https://folia.unifr.ch/unifr/documents/328989
Statistics
Document views: 16
File downloads:
- mc_0.pdf: 61