查看文章

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 -complete. While Matching Cut is trivial for graphs with minimum degree at most one, it is -complete on graphs with minimum degree two. In this paper, we show that, for any given constant , Matching Cut is -complete in the class of graphs with minimum degree c and this restriction of Matching Cut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant , Matching Cut remains -complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree . We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree in time, where is the positive root of the polynomial . Despite the …