Karp hardness of searching for a matching cut Follow-up question in the series:
Karp hardness of searching for a matching erosion
Karp hardness of searching for a matching split

Maximum Matching Cut problem
Input: An undirected graph $G(V, E)$ and an integer $k$
Output: YES if there exists $M \subseteq E$ such that $M$ is a matching of size $k$ (i.e. $k$ edges) and also a cut, NO otherwise

What is the complexity of this problem? (Turing completeness was established, what can we tell about its Karp hardness?)

An edge cut is a subset of $E$ the removal of which would increase the number of connected component of $G$, and for each edge in the set, its two endpoints are in (two) different components.
You can reduce the problem without cardinality constraint to the problem with cardinality constraint.

For an instance $G=(V,E)$ of the problem without cardinality constraint, simply add $m&gt;|V|/2$ isolated edges as well as $2m$ new vertices. Now there is a matching cut in the old graph if and only if there is a matching cut of size $m+1$ in the new graph.



Edit: One can also add an edge $(u,v)$ for each newly added edge $(u,x)$ and a fixed vertex $v$ in the previous graph to make $G$ connected. The conclusion is the same.