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 is defined to be a matching subgraph of that is also the edge set of a cut. A cut of a graph is a partition of the vertex set into two sets such that and 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 is then defined to be the subset of containing all the edges with one endpoint in and the other endpoint in , i.e. those edges with and . 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 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 matching erosion as a matching cut such that is exactly one side of the matching. It means that each vertex has exactly one edges out of , and for any two different vertices their crossing edges end in different vertices in . Intuitively, such a matching erosion visually ”peels” off from .
Formally, we define a matching erosion of an undirected graph as follows:
Given an undirected graph , a matching erosion is a partition of into two disjoint sets such that:
and are two disjoint induced subgraphs
The edge set of the cut is a matching: is a matching
Every is incident to an edge in
Then, our problem naturally asks whether a given undirected graph has a matching erosion.
Matching Erosion of a graph:
Input: An undirected graph
Output: Yes if has a matching erosion , 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 and a collection of subsets of . Each subset in contains exactly elements . The decision problem asks whether there exists a subcollection such that each element of is contained in exactly one subset in . Obviously, will contain exactly subsets in the collection . Such a collection is called an exact cover of .
Exact 3-Set Cover problem:
Input: a universe and a collection of subsets of , where each contains elements
Output: Yes if there exists an exact cover , 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.
We have that Exact 3-Set Cover Matching Erosion
Reducing EXACT 3-SET COVER to MATCHING EROSION
In this section, we prove the claim 4.
Describing the construction: Given an instance of Exact 3-Set Cover, we will construct an undirected graph as the produced instance of our problem Matching Erosion. For each element in the universe , we create a new vertex . Similarly, for each subset , we create a new consisting of 3 new vertices . For each such subset , we add the edges to , namely . Finally, we add all edges between pairs of two different vertices of the ‘s vertices to turn these into a clique.
Correctness of the construction:
Suppose that has an exact cover consistig of subsets in , then based on that solution to Exact 3-Set Cover, we will easily construct a solution to the produced instance of our problem Matching Erosion. Namely, our matching erosion for would have to be the set of all the ‘s of the subsets included in the exact cover. Clearly, each vertex (where is included in the exact cover and ) in this set is connected to exactly one vertex outside of , namely its corresponding element in the universe . Obviously, this is a matching cut that happens to be also a matching erosion.
Conversely, if has a matching erosion , we shall show that none of the elements in the universe is included in . Indeed, if some is included in then at most one is not in . This is because if there exist and then cannot form one side of a matching erosion since is incident to two crossing edges , , recall that the universe is turned into a in . So, if one element in is included in , at most one element can be in , but this is also clearly not the case. Because if so, then all the other element ‘s (which are included in ) are connected to violating the definition of a matching erosion. So, we have shown that if some element is included in , then all of the corresponding to in are included in . But, this also cannot be the case for a matching erosion. We need the following observation.
Observation: For each corresponding to a subset , a vertex in this is included in iff. all the three vertices of this are included in .
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 to . Indeed, if so, the matching erosion will then partition the ‘s into two disjoint sets of ‘s, those in and those in . The ‘s in would then intuitively form an exact cover for . But, unfortunately, in this case, those vertices of the in cannot have any crossing edge in , thus violating the definition of a matching erosion.
We have therefore shown that none of the elements in the universe is included in . This implies that contains all the . So, the matching erosion needs to partition the set of ‘s into two disjoint sets of ‘s, those in and those in like before. But fortunately, the situation is now reversed. the ‘s in does not need any crossing incident edge (this is only required in a matching split that also imposes the same requirement of for ). And, the ‘s in would form an exact cover for .