On Structural Parameterizations of the Matching Cut Problem


In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The matching cut problem is the problem of deciding whether a given graph has a matching cut. The matching cut problem can be expressed using a monadic second-order logic (MSOL) formula and hence is solvable in linear time for graphs with bounded tree-width. However, this approach leads to a running time of $f(\phi,t)n^{O(1)}$, where $\phi$ is the length of the MSOL formula, $t$ is the tree-width of the graph and $n$ is the number of vertices of the graph.
In [Theoretical Computer Science, 2016], Kratsch and Le asked to give a single exponential algorithm for the matching cut problem with tree-width alone as the parameter. We answer this question by giving a $2^{O(t)}n^{O(1)}$ time algorithm. We also show the tractability of the matching cut problem when parameterized by neighborhood diversity and other structural parameters.

Proceedings of the 11th International Conference on Combinatorial Optimization and Applications - COCOA 2017, Shanghai, China