Finding Perfect Matching Cuts Faster

Abstract

Joint work with Yash More ⸱ To Appear at IWOCA 2023 ⸱ Preprint coming soon!

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. We demonstrate a faster exact exponential time algorithm on general graphs and an even faster algorithm on graphs of maximum degree three that have girth six.