On Conflict-Free Cuts: Algorithms and Complexity

Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza

One way to define the Matching Cut problem is: Given a graph $G$, is there an edge-cut $M$ of $G$ such that $M$ is an independent set in the line graph of $G$? We propose the more…