Matching Cuts in Graphs of High Girth and H-Free Graphs
share
The (Perfect) Matching Cut is to decide if a graph has a (perfect) matching that is also an edge cut. The Disconnected Perfect Matching problem is to decide if a 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 graphs of arbitrarily large fixed girth. We prove the last result also for the other two problems, solving a 20-year old problem for Matching Cut. Moreover, we give three new general hardness constructions, which imply that all three problems 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. Finally, by combining our new hardness construction for Perfect Matching Cut with two 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.
READ FULL TEXT