Matching cut: Kernelization, single-exponential time FPT, and exact exponential algorithms
Christian Komusiewicz, Dieter Kratsch, Van Bang Lê · Discrete Applied Mathematics · 2019
In a graph, a matching cut is an edge cut that is a matching. Matching Cut, which is known to be NP-complete, is the problem of deciding whether or not a given graph G has a matching cut. In this paper we show that Matching Cut admits a quadratic-vertex kernel for the parameter distance to cluster and a linear-vertex kernel for the parameter distance to clique. We further provide an O^*(2^{dc(G)}) time and an O^*(2^{dc^-}(G)}) time FPT algorithm for Matching Cut, where dc(G) and dc^-(G) are the distance to cluster and distance to co-cluster, respectively. We also improve the running time of the best known branching algorithm to solve Matching Cut from O^*(1.4143^n) to O^*(1.3803^n). Moreover, we point out that, unless NP subseteq coNP/poly, Matching Cut does not admit a polynomial kernel when parameterized by treewidth.