Matching Cuts in Graphs of High Girth and H-Free Graphs
BP2-STS
- Feghali, Carl ORCID University of Lyon, EnsL, CNRS, LIP, France
- Lucke, Felicia ORCID University of fribourg, Switzerland
- Paulusma, Daniël ORCID Durham University, UK
- Ries, Bernard ORCID University of Fribourg, Switzerland
- Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023
Published in:
- 34th International Symposium on Algorithms and Computation (ISAAC 2023). - Leibniz International Proceedings in Informatics (LIPIcs). - 2023, vol. 283, no. 31, p. 31:1–31:16
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 NP-complete 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 NP-complete 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 largest matching 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.
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 NP-complete 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 NP-complete 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 largest matching 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
- License undefined
- Open access status
- green
- Identifiers
-
- DOI 10.4230/LIPIcs.ISAAC.2023.31
- ISSN 1868-8969
- Persistent URL
- https://folia.unifr.ch/unifr/documents/329096
Statistics
Document views: 13
File downloads:
- lipics.isaac.2023.31.pdf: 27