Karp hardness of searching for a matching split

Question

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?

Answer 1

It is NP-complete. Clearly it belongs to NP. To prove its NP-completeness, we'll reduce not-all-equal 3-satisfiability (NAE3SAT) to this problem.

Given an instance of NAE3SAT with $n$ variables and $m$ clauses, construct a graph as follows:

1. For each literal $l$, construct a complete graph with $m+1$ vertices $v_0(l),\ldots,v_m(l)$.

2. For each variable whose positive and negative literals are respectively $l_i$ and $l_j$, add an edge between $v_0(l_i)$ and $v_0(l_j)$.

3. For each clause $c_i=l_i^1\vee l_i^2\vee l_i^3$, add the following structure:

   In addition, for each literal $l$ other than $l_i^1,l_i^2,l_i^3$, add a new vertex $v_i'(l)$ and an edge between $v_i(l)$ and $v_i'(l)$.

Now we assert that the instance of NAE3SAT is satisfiable if and only if the graph has a matching split.

If the instance of NAE3SAT is satisfiable, consider a valid truth assignment. If $l$ is a truth literal, we put $v_i(l)$'s into $A$ and $v_i'(l)$'s (if exists) into $B$ for all $i=0,\ldots,m$, otherwise we put $v_i(l)$'s into $B$ and $v_i'(l)$'s into $A$. In addition, for the structure corresponding to $c_i$ (we assume $l_i^1$ and $l_i^2$ are truth literals while $l_i^3$ is a false literal without loss of generality), we put $v_i^{12}, v_i^{123}$ into $A$ and put $v_i^{23}, v_i^{31}, v_i^{122331}$ into $B$. We can see this partition is a matching split.

If the graph has a matching split, we can observe firstly that $v_0(l),\ldots,v_m(l)$ should be put into the same part since they make up a complete graph (assume $m\ge 2$ without loss of generality). In addition, if $l_i$ and $l_j$ correspond respectively to the positive and negative literals of the same variable, $v_k(l_i)$ and $v_k(l_j)$ should be put into different parts otherwise $v_0(l_i)$ or $v_0(l_j)$ has no neighbor in the other part. If the positive literal corresponding to a variable is put into $A$, we assign the variable to True, otherwise we assign it to False. Note for each clause $c_i$, $v_i(l_i^1), v_i(l_i^2)$ and $v_i(l_i^3)$ cannot be put into the same part otherwise $v_i^{123}$ has either no neighbor or $3$ neighbors in the other part. Hence this assignment is a valid assignment for the instance of NAE3SAT.

---

Edit: One can simply add edges among $v_0(l)$'s to make the graph connected. For example, if the clauses are $l_1\vee l_2\vee l_3$ and $l_4\vee l_5\vee l_6$, one can simply add an edge between $v_0(l_3)$ and $v_0(l_4)$. The idea is that for a valid assignment, if we flip all the values of variables involved in one connected component, the assignment is still valid. In the example, this means we can always assume $v_0(l_3)$ and $v_0(l_4)$ are put into the same part.