Conference paper (in proceedings)
Finding Matching Cuts in H-Free Graphs
BP2-STS
Published in:
- 33rd International Symposium on Algorithms and Computation (ISAAC 2022). - Schloss Dagstuhl - Leibniz-Zentrum für Informatik. - 2022, p. 22:1-22:16
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 NP-complete for Pr-free graphs. This addresses a question of Bouquet and Picouleau (arXiv, 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
-
-
Classification
-
Computer science and technology
-
License
-
CC BY
-
Open access status
-
green
-
Identifiers
-
-
Persistent URL
-
https://folia.unifr.ch/unifr/documents/322855
Statistics
Document views: 47
File downloads:
- lipics-isaac-2022-22.pdf: 98