Matching Cuts in Graphs of High Girth and H-Free Graphs
BP2-STS
- Feghali, Carl ORCID University of Lyon, EnsL, CNRS, LIP, 69342 Lyon Cedex 07, France
- Lucke, Felicia ORCID Department of Informatics, University of Fribourg, Fribourg, Switzerland
- Paulusma, Daniël ORCID Department of Computer Science, Durham University, Durham, UK
- Ries, Bernard ORCID Department of Informatics, University of Fribourg, Fribourg, Switzerland
- 2025
Published in:
- Algorithmica. - Springer Science and Business Media LLC. - 2025
English
The (Perfect) Matching Cut problem is to decide if a connected graph has a (perfect) matching that is also an edge cut. The Disconnected Perfect Matching problem is to decide if a connected graph has a perfect matching that contains a matching cut. Both Matching Cut and Disconnected Perfect Matching are NP-complete for planar graphs of girth 5,whereas Perfect Matching Cut is known to be NP-complete even for subcubic bipartite graphs of arbitrarily large fixed girth. We prove that Matching Cut and Disconnected Perfect Matching are also NPcomplete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Our result for Matching Cut resolves a 20-year old open problem. We also show that the more general problem d- Cut, for every fixed d ≥ 1, is NPcomplete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Furthermore, we show that Matching Cut, Perfect Matching Cut and Disconnected Perfect Matching are NP-complete for H-free graphs whenever H contains a connected component with two vertices of degree at least 3. Afterwards, we update the state-of-the-art summaries for H-free graphs and compare them with each other, and with a known and full classification of the Maximum Matching Cut problem, which is to determine a largestmatching cut of a graph G. Finally, by combining existing results,we obtain a complete complexity classification of Perfect Matching Cut for H-subgraph-free graphs where H is any finite set of 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-025-01318-8
- ISSN 0178-4617
- Persistent URL
- https://folia.unifr.ch/unifr/documents/331960
Statistics
Document views: 7
File downloads:
- feghali_et_al-2025-algorithmica_0.pdf: 12