In the theory of finite undirected graph, a basic notion that is broadly studied is the notion of matching cut. A matching cut in a graph $G$ is defined to be a matching subgraph of $G$ that is also the edge set of a cut. A $\it cut$ of a graph $G = (V, E)$ is a partition of the vertex set $V$ into two sets $(A, B)$ such that $A$ and $B$ induces two disjoint induced subgraphs that were before incident to some crossing edges which are the edges in the corresponding so-called edge cut set. Specifically, the edge set of the cut $(A, B)$ is then defined to be the subset of $E$ containing all the edges with one endpoint in $A$ and the other endpoint in $B$, i.e. those edges $uv$ with $u\in A$ and $v\in B$. A matching cut is formally defined to be the edge set of such a cut, whenever its edge cut set is indeed a matching. It is worth noting that a matching subgraph which removal increases the number of connected components of a graph $G$ is not necessarily a matching cut, since it may contain edges inside the two separated induced subgraphs. It is a matching cut if it contains exactly the edges of the cut. In order to have more hard computational problems in our still very limited arsenal of proven hard problems, we want to restrict this notion further. We define a {\it matching erosion} as a matching cut $(A, B)$ such that $A$ is exactly one side of the matching. It means that each vertex $v\in A$ has exactly one edges out of $A$, and for any two different vertices $u, v\in A$ their crossing edges end in different vertices in $B$. Intuitively, such a matching split $M=(A,B)$ visually ''peels" off $A$ from $G$.
Formally, we define a matching erosion of an undirected graph as follows:
DEFINITION 1
Given an undirected graph $G=(V, E)$, a matching erosion $(A, B)$ is a partition of $V$ into two disjoint sets $V = A\cup B$ such that:
- $G[A]$ and $G[B]$ are two disjoint induced subgraphs
- The edge set of the cut is a matching: $M = \{uv\in E\vert u\in A \land v\in B\}$ is a matching
- Every $u\in A$ is incident to an edge in $M$
Then, our problem naturally asks whether a given undirected graph $G$ has a matching erosion.
DEFINITION 2
Matching Erosion of a graph:
Input: An undirected graph $G(V, E)$
Output: Yes if $G$ has a matching erosion $(A, B)$, otherwise No
In the next section, we will show that Matching Erosion is computationally hard.
We will reduce Exact 3-Set Cover problem to our problem. Exact 3-Set Cover is another decision problem defined as follows. In Exact 3-set Cover, we are given a universe set of elements $U=\{e_1, e_2, \dots, e_{3n}\}$ and a collection $F=\{s_1, s_2, \dots, s_m\}$ of subsets of $U$. Each subset $s_j$ in $F$ contains exactly $3$ elements $e_{s_j1}, e_{s_j2}, e_{s_j3}\in U$. The decision problem asks whether there exists a subcollection $F'\subseteq F$ such that each element $e_i$ of $U$ is contained in exactly one subset $s_j$ in $F'$. Obviously, $F'$ will contain exactly $n$ subsets in the collection $F$. Such a collection $F'$ is called an exact cover of $U$.
DEFINITION 3
Exact 3-Set Cover problem:
Input: a universe $U = \{e_1, e_2, \dots, e_{3n}\}$ and a collection $F=\{s_1, s_2, \dots, s_m\}$ of subsets of $U$, where each $s_j$ contains $3$ elements $e_{s_j1}, e_{s_j2}, e_{s_j3}\in U$
Output: Yes if there exists an exact cover $F'\subseteq F$, otherwise No
Exact 3-Set Cover is shown to be hard by Garey and Johnson. After describing and proving the correctness of the reduction in the next section, we will establish the following claim.
CLAIM 4
We have that Exact 3-Set Cover $\leq_p$ Matching Erosion
Reducing EXACT 3-SET COVER to MATCHING EROSION
In this section, we prove the claim 4.
Proof:
Describing the construction: Given an instance $(U, F)$ of Exact 3-Set Cover, we will construct an undirected graph $G=(V, E)$ as the produced instance of our problem Matching Erosion. For each element $e_i$ in the universe $U$, we create a new vertex $e_i\in V$. Similarly, for each subset $s_j\in F$, we create a new $K_3$ consisting of 3 new vertices $s_{j,1}, s_{j,2}, s_{j,3}\in V$. For each such subset $s_j = \{e_{s_j1}, e_{s_j2}, e_{s_j3}\}$, we add the $3$ edges to $E$, namely $s_{j,1}e_{s_j1},\:s_{j,2}e_{s_j2},\:s_{j,3}e_{s_j3}$. Finally, we add all edges between pairs of two different vertices of the $e_i$'s vertices to turn these into a $K_{3n}$ clique.
Correctness of the construction:
Suppose that $(U, F)$ has an exact cover $F'\subseteq F$ consistig of $n$ subsets in $F$, then based on that solution to \textsc{Exact 3-Set Cover}, we will easily construct a solution to the produced instance $G(V, E)$ of our problem Matching Erosion. Namely, our matching erosion for $G$ would have $A$ to be the set of all the $K_3$'s of the subsets included in the exact cover. Clearly, each vertex $s_{j,k}$ (where $s_j$ is included in the exact cover and $1\leq k\leq 3$) in this set $A$ is connected to exactly one vertex outside of $A$, namely its corresponding element $e_{s_jk}$ in the universe $U$. Obviously, this is a matching cut that happens to be also a matching erosion.
Conversely, if $G(V, E)$ has a matching erosion $M = (A, B)$, we shall show that none of the elements $e_i$ in the universe is included in $A$. Indeed, if some $e_i$ is included in $A$ then at most one $e_l$ is not in $A$. This is because if there exist $e_i\in A$ and $e_{l1}, e_{l2}\not\in A$ then $A$ cannot form one side of a matching erosion since $e_i\in A$ is incident to two crossing edges $e_ie_{l1}$, $e_ie_{l2}$, recall that the universe $U$ is turned into a $K_{3n}$ in $G$. So, if one element in $U$ is included in $A$, at most one element $e_l$ can be in $B$, but this is also clearly not the case. Because if so, then all the other element $e_i$'s (which are included in $A$) are connected to $e_l\in B$ violating the definition of a matching erosion. So, we have shown that if some element $e_i$ is included in $A$, then all of the $K_{3n}$ corresponding to $U$ in $G$ are included in $A$. But, this also cannot be the case for a matching erosion. We need the following observation.
Observation: For each $K_3$ corresponding to a subset $s_j$, a vertex $s_{j,k}$ in this $K_3$ is included in $A$ iff. all the three vertices of this $K_3$ are included in $A$.
Proof (of the observation):
Obviously, by definition of a matching erosion.
Using this observation, we are able to show that a matching erosion cannot include all the $K_{3n}$ to $A$. Indeed, if so, the matching erosion will then partition the $K_3$'s into two disjoint sets of $K_3$'s, those in $A$ and those in $B$. The $K_3$'s in $B$ would then intuitively form an exact cover for $U$. But, unfortunately, in this case, those vertices of the $K_3$ in $A$ cannot have any crossing edge in $M$, thus violating the definition of a matching erosion.
We have therefore shown that none of the elements $e_i$ in the universe is included in $A$. This implies that $B$ contains all the $K_{3n}$. So, the matching erosion needs to partition the set of $K_3$'s into two disjoint sets of $K_3$'s, those in $A$ and those in $B$ like before. But fortunately, the situation is now reversed. the $K_3$'s in $B$ does not need any crossing incident edge (this is only required in a matching split). And, the $K_3$'s in $A$ would form an exact cover for $U$.
