Soptq

Vertex Cover Problem (Vertex Cover) is described as follows: Given $<G,k>$, where $G$ is an undirected graph, the question is whether there exists a set of vertices $V$, $\lvert V \rvert <= k$, such that every vertex in $V$ covers all the edges in $G$. That is, every edge in $G$ has at least one endpoint in $V$. In the example below, $<A,B>$ is a set that satisfies this condition because each of the 4 edges in the graph is connected to at least one point in $<A,B>$.

To prove its NP-completeness, we first prove that it is an NP problem. Given a $G$ and a $V$, we only need to traverse each edge in $G$ and check if it is connected to a point in $V$ to determine the correctness of $V$. Obviously, this process can be completed in polynomial time, so the Vertex Cover problem is an NP problem.

Next, to prove that it is an NP-hard problem, we reduce 3-SAT to the Vertex Cover problem. The form of 3-SAT is as follows:

$\begin{cases} C = C_1 \cap C_2 \cap \cdots \cap C_n \\ C_i = x_a^i \cup x_b^i \cup x_c^i \end{cases}$

Given a 3-SAT expression, we perform the following operations:

1. Connect each of the three variables in each cluster.
2. Connect inconsistent same variables in different clusters. Inconsistent means that if there are two different clusters with the same variable $x_a^i$ and $x_a^j$, if $x_a^i$ is true, then $x_a^j$ is false; if $x_a^i$ is false, then $x_a^j$ is true.

In this way, we convert a 3-SAT boolean expression into a graph, where $k = 2n$ and $n$ is the number of clusters in the boolean expression. For example, if a 3-SAT boolean expression is:

$C=(x+y+z) \cdot (\overline{x}+\overline{y}+\overline{z}) \cdot (x+\overline{y}+z) \cdot (\overline{x}+y+\overline{z})$

Then, according to the above rules, the graph constructed for $C_1$ is:

Now, let's prove two statements:

(1) If a 3-SAT problem has a solution, then the converted graph $G$ also has a solution to the Vertex Cover problem. Since we have a solution to the 3-SAT problem, i.e., $C = 1$, then for each cluster in this 3-SAT, at least one variable is true. We take the other two variables in each cluster as members of the Vertex Cover problem $V$, and in total we have $2n$ members. Since each cluster in the graph forms a triangle, selecting two vertices from the three vertices of the triangle will definitely cover all the edges of the triangle. On the other hand, for each variable, it is connected to the same variable in a different cluster that is inconsistent with it. So as long as the 3-SAT problem has a solution, for each variable, regardless of its value, it will definitely be connected to the inconsistent same variable (for example, regardless of whether $x$ is true or false, it will be connected to $\overline{x}$). Therefore, $G$ satisfies $k = 2n$ as long as the corresponding 3-SAT problem is satisfied.

(2) If a Vertex Cover problem $<G, k>$ has a solution, then the converted 3-SAT problem also has a solution. We can reverse the transformation of $<G,k>$ into a boolean expression using the above rules, and set the variables corresponding to the vertices in $G$ that do not belong to $V$ to true. Then the 3-SAT problem will be true.

In conclusion, we have reduced the 3-SAT problem to the Vertex Cover problem. Therefore, the Vertex Cover problem is NP-complete.