UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (UTC is now 17 Sep 01:57)
This is yet another follow-up question in the series:
Karp hardness of searching for a matching cut
Karp hardness of searching for a matching erosion
In this question, we further restrict the notion of a matching erosion (which is already a restricted notion of a matching cut). Formally, our definition is as follows.
Given an undirected graph $G(V, E)$, a matching split $M=(A, B)$ is a partition of $V$ into two disjoint subsets, i.e. $A\cap B = \emptyset \land A\cup B = V$ that satisfies the following conditions:
- $G[A]$ and $G[B]$ are two disjoint induced subgraphs
- The edge set of the cut $M = \{uv\in E\vert u\in A \land v \in B\}$ is a matching (here, we abuse the notation a little bit, $M$ is both the partition $(A, B)$ and the edge set of the matching cut)
- Each vertex $u\in A$ is incident to exactly one edge in $M$
- Each vertex $u\in B$ is incident to exactly one edge in $M$
Clearly, we should have $|A|=|B|=|V|/2$, hence the name of this concept.
Our decision problem Matching Split naturally asks whether a given graph $G$ has a matching split.
Our question is: What is the complexity of deciding Matching Split?