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.