3
$\begingroup$

First, read the previous question: Karp hardness of searching for a matching cut

As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the problem has been proven to be $\mathrm{NP}$-hard even when restricted to bipartite graph of bounded diameter.

Now, I wanna restrict the notion of a matching cut even further to a matching erosion. A matching erosion is a matching cut whose removal separates the original graph into two connected components $A$ and $B$, where all the vertices of $A$ belong to the matching itself. In other words, a matching erosion is just a matching cut that peels off $A$ from $G$ like cutting a thin slice of meat off a big meat block in a cafe bar.

All the literature constructions seem not to be able to yield such a nice, thin matching erosion cut.

Our problem is defined as: Given an undirected graph, determining if there exists a matching erosion.

The question is what is the complexity of our problem?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

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.