3
$\begingroup$

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?

$\endgroup$
3
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But note that we are drifting further away from literature notion of a clean matching cut (resulting into exactly $2$ components). See my updated answer to the prequel question. $\endgroup$ – Thinh D. Nguyen Sep 17 '18 at 1:48
  • $\begingroup$ @ThinhD.Nguyen Added the reduction for connected graph. $\endgroup$ – xskxzr Sep 17 '18 at 3:45
  • $\begingroup$ So, the crucial difficulty is a matching cut that results in exactly $2$ components. Connectedness can be easily adapted. $\endgroup$ – Thinh D. Nguyen Sep 17 '18 at 3:54
  • $\begingroup$ @ThinhD.Nguyen You can ask another question for exactly 2 components. $\endgroup$ – xskxzr Sep 17 '18 at 3:57
  • $\begingroup$ In 2 days, if a sharper answer is provided, then clearly that answer is much better and deserve the bounty. Even if so, your answer is the accepted one. Posting a quite similar other post (just adding one requirement) would receive close votes from moderators. $\endgroup$ – Thinh D. Nguyen Sep 17 '18 at 4:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.