Algorithms Solving the Matching Cut Problem
In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP-complete. This paper provides a first branching algorithm solving Matching Cut in time $$O^*2^{n/2}=O^*1.4143^n$$ for an $$n$$-vertex input graph, and shows that Matching Cut parameterized by vertex cover number $$\tau G$$ can be solved by a single-exponential algorithm in time $$2^{\tau G} On^2$$. Moreover, the paper also gives a polynomially solvable case for Matching Cut which covers previous known results on graphs of maximum degree three, line graphs, and claw-free graphs.