Karp hardness of searching for a matching cut

Question

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.

Answer 1

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>|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.

Answer 2

This is not supposed to be an answer (eventually, being satisfied enough with the literature and my own's new result, I accept this). But, I wanna mention a very closely related result. Namely, without the requirement of cardinality $k$, the problem is NP-complete.

However, using their result, it is immediately that our problem is Turing-complete for $\mathrm{NP}$. The poly-time Turing reduction just query our problem (as an oracle) of every possible $k$.

The Maurizio duo of Roma Tre showed our problem (without the cardinality requirement) to be $\mathrm{NP}$-complete in the paper titled "The Complexity of the Matching-Cut Problem" (pdf file)

What makes their hardness proof not guarantees the cardinality requirement $k$ is that the cardinality of the matching cut inside each clause-gadget (the A, B, C, D, E, F cut types in Table 1 in the paper) can have cardinality of $4$ or $6$. So, we cannot include any cardinality indication $k$ to the produced instance.

---

UPDATE: There is also literature proof that Maurizio duo's hardness can be proven even when restricted to bipartite graphs of bounded diameter. Though, it is unclear how bipartiteness can help in our problem. Link to the latest article on this topic: https://arxiv.org/pdf/1804.11102.pdf

---

UPDATE: xskxzr's answer finally settle down Karp hardness for this problem. Strictly speaking, literature notion of a matching cut requires that the given graph to be connected and the resulted graph to be split into exactly $2$ connected components. If more than two components are allowed. Then, based on the idea of xskxzr, I have managed to extend the construction of Maurizio duo of Roma Tre. Just extend the False chain and True chain to the left (or right, it does not matter) but the new vertices only have single edges link (not doubly linked) and each pair (one in the true chain, one in the false chain) is connected by $3$ edges with $2$ new nodes in between. Then, we can extend these two chains to a long enough length, to safely produce a required cardinality $K$. Since to separate the two chains, we can cut through the "middle" edges and finally when "nearly" reaching $K$, cut $2$ edges that link to the further new vertices. It seems to be difficult to reduce under the requirement of connectedness and a clean cut (exactly into $2$ components).