The description of the "Clique Problem" is as follows: Given <G, k>, where G is an undirected graph, we want to determine if there exists a set of vertices V that forms a clique, with |V| <= k. In other words, are the points in V mutually connected? The example graph below shows an example of a valid set of points, <B, C, D, E>, because these four points are mutually connected and form a clique.
First, in order to prove that it is NP-complete, we need to show that it is an NP problem. If we are given a set of vertices V, where |V| <= k, we can simply check if each point in V is connected to every other point, which can be verified in polynomial time. Therefore, the verification step can be completed in polynomial time, making the Clique Problem an NP problem.
Next, we will reduce the 3-SAT problem to the Clique Problem to prove that the Clique Problem is NP-hard. First, we know that the 3-SAT problem has the following form:
C = C1 ∩ C2 ∩ ... ∩ Cn
Ci = xa ∪ xb ∪ xc
Given a 3-SAT expression, for any two variables xa and xb, we have:
- If i ≠ j
- If a = b, then xa and xb are consistent. Consistency means that when xa is true, xb is also true; when xa is false, xb is also false.
In this case, we connect xa and xb. This way, we can convert a 3-SAT boolean expression into a graph. For example, if a 3-SAT boolean expression is:
C = (x+y+z)⋅(¬x+¬y+¬z)⋅(x+¬y+z)⋅(¬x+y+¬z)
The graph created according to the above rules would be:
Now, we need to prove two things: 1) If there exists a solvable 3-SAT with k clusters (k Ci), then the graph G converted from it can solve the Clique Problem <G, k>. 2) If there exists a solvable Clique Problem <G, k>, then we can always convert it to a solvable 3-SAT.
For (1), if the given 3-SAT has a solution, according to the definition of 3-SAT, in order for the boolean expression to be true, each cluster must be true, meaning that at least one variable in each cluster must be true. Therefore, we can circle the variable that is true in the graph. For the example mentioned above, the graph with one solution circled would look like:
According to the rules of converting 3-SAT to G, each variable is connected to all other variables that are not in the same cluster and are not contradictory. Therefore, we can guarantee that the selected points can form a clique (mutually connected).
For (2), if we are given a solvable Clique Problem <G, k>, we can reverse the conversion rules and convert G into a boolean expression, and assign true to the variables corresponding to the points in V. Because the points in V are mutually connected, according to the rules, they are neither in the same cluster nor contradictory, so we can guarantee that the boolean expression will be true.
In conclusion, we have successfully reduced 3-SAT to the Clique Problem, proving that the Clique Problem is NP-complete.