Félicia Lucke (LIP, ENS Lyon)

The problem Matching Cut asks for an edge set of a graph which is both an edge cut and a matching. An edge cut is a set of edges whose deletion disconnects the graph and a matching is a set of edges in which no two edges share an endpoint.

We consider the two recent optimisation variants Maximum and Minimum Matching Cut, where we aim to maximise, respectively minimise, the number of edges in the matching cut. Both variants are NP-hard but differ in complexity for certain graph classes. In this talk we investigate why maximising is harder than minimising. We further compare the optimisation variants of Matching Cut to the classical Matching Cut and its oldest variant Perfect Matching Cut.