Finding Perfect Matching Cuts Faster

A cut (X, Y) is a perfect matching cut if and only if each vertex in X has exactly one neighbor in Y and each vertex in Y has exactly one neighbor in X. The computational problem of determining if a graph admits a perfect matching cut is NP-complete, even when restricted to the class of bipartite graphs of maximum degree 3 and arbitrarily large girth. Assuming ETH, the problem does not admit an algorithm subexponential in n. On the other hand, the problem is known to be polynomial-time solvable when restricted to interval graphs, permutation graphs, and some other special classes of graphs. It is also known to be FPT parameterized by treewidth or cliquewidth and in XP when parameterized by mim-width (maximum induced matching-width) of a given decomposition of the graph. The ETH-hardness of the problem has motivated the study of exact algorithms for PMC, and the best-known running time has complexity (We use the O^∗ notation which suppresses polynomial factors.) O^∗(1. 2721 ⁿ) [Le and Telle, WG 2021]. In this contribution, we design a mildly improved branching algorithm using an arguably simpler approach, whose running time is O^∗(1. 2599 ⁿ). This addresses an open problem posed by Le and Telle. We also demonstrate an O^∗(1. 1938 ⁿ) algorithm for graphs of maximum degree 3 that have girth at least six.