2026-07-23T01:24:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19333 2024-03-06T11:03:47Z ddc:004 open_access

Matching Cuts in Graphs of High Girth and H-Free Graphs Feghali, Carl Lucke, Felicia Paulusma, Daniël Ries, Bernard matching cut perfect matching girth H-free graph 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Carl Feghali and Felicia Lucke and Daniël Paulusma and Bernard Ries 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.31 urn:nbn:de:0030-drops-193332 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.31 eng https://creativecommons.org/licenses/by/4.0/legalcode