The complexity of the Perfect Matching-Cut problem
Preprint
Abstract
Perfect Matching-Cut is the problem of deciding whether a graph has a perfect matching that contains an edge-cut. We show that this problem is NP-complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five-regular graphs, for graphs of diameter three and for bipartite graphs of diameter four. We show that there exist polynomial time algorithms for the following classes of graphs: claw-free, $P_5$-free, diameter two, bipartite with diameter three and graphs with bounded tree-width.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and KernelizationAlgorithmica, 2021
- A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameterTheoretical Computer Science, 2019
- A New Characterization of $P_k$ P k -Free GraphsAlgorithmica, 2015
- Graph Structure and Monadic Second-Order Logic2012
- Extremal graphs having no matching cutsJournal of Graph Theory, 2011
- The complexity of the matching‐cut problem for planar graphs and other graph classesJournal of Graph Theory, 2009
- On stable cutsets in line graphsTheoretical Computer Science, 2003
- Disconnected 2-Factors in Planar Cubic Bridgeless GraphsJournal of Combinatorial Theory, Series B, 2002
- Dominating cliques in P5-free graphsPeriodica Mathematica Hungarica, 1990
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973