Question

Consider the CLIQUE problem restricted to graphs in which every vertex has degree at most v. Call this problem CLIQUE-3 .

(a) Prove that CLIQUE-3 is in NP .

(b) What is wrong with the following proof of NP-completeness for CLIQUE-3 ? We know that the CLIQUE problem in general graphs is NP-complete, so it is enough to present a reduction from CLIQUE-3 to CLIQUE . Given a graph G with vertices of degree $\mathbf{\le }\mathbf{3}$, and a parameter g, the reduction leaves the graph and the parameter unchanged: clearly the output of the reduction is a possible input for the CLIQUE problem. Furthermore, the answer to both problems is identical. This proves the correctness of the reduction and, therefore, the NP-completeness of CLIQUE-3 .

(c) It is true that the VERTEX COVER problem remains NP-complete even when restricted to graphs in which every vertex has degree at most 3 . Call this problem VC-3 . What is wrong with the following proof of NP-completeness for CLIQUE ? We present a reduction from VC-3 to CLIQUE-3 . Given a graph G=(V,E) with node degrees bounded by 3 , and a parameter b , we create an instance of CLIQUE-3 by leaving the graph unchanged and switching the parameter to $\left|V\right|\mathbf{-}\mathbf{b}$. Now, a subset $\mathit{C}\mathbf{\subseteq }\mathit{V}$is a vertex cover in G if and only if the complementary set V-C is a clique in G. Therefore G has a vertex cover of $\mathbf{size}\mathbf{\le }\mathbf{b}$if and only if it has a clique of size $\mathbf{\ge }\left|V\right|\mathbf{-}\mathbf{b}$. This proves the correctness of the reduction and, consequently, the NP-completeness of CLIQUE-3 .

(4)Describe an $\mathbf{O}\left(\left|V\right|\right)$algorithm for CLIQUE-3 .

Short answer

(a) It is proved that the CLIQUE-3 problem is in NP.

(b) The given proof of CLIQUE-3 being an NP-complete problem does not prove anything.

(c) The proof using the vertex cover is incorrect.

(d) An algorithm for the CLIQUE-3 runs in$O\left({\left|v\right|}^4\right)$ is described.

Step-by-step solution

To prove CLIQUE-3 as NP-Complete Problem

(a)

Consider the information:

The problem is called NP if its solution can be obtained and verified in polynomial time.

The objective is to prove that a CLIQUE-3 problem in which every vertex has a degree at most 3 is in NP.

Proof:

The solution to the CLIQUE-3 problem requires identifying that if there is an edge between every pair of vertices.

Verify each node in the clique by visiting them and counting how many times the nodes are connected via edges.

This verification completes in polynomial time and the numbers of cliques are also polynomial due to the restriction of at most 3 edges.

So, the verifier runs in polynomial time.

Therefore, the CLIQUE-3 problem is in NP.

Given prove doesn’t justify CLIQUE-3 being NP-Complete Problem

(b)

Consider the information:

The computer system can solve only those problems whose polynomial time solution is available.

So, the problems that do not have an efficient solution are called the NP-complete problems.

If a problem is a polynomial-time reducible to an NP problem, then it is called an NP-complete problem.

Issue with the proof:

The given proof of the CLIQUE-3 problem of being NP-complete tells that the CLIQUE problem is at least as hard as the CLIQUE-3.

It says that the reduction of problem CLIQUE-3 to CLIQUE leaves the graph and the parameter unchanged, which is wrong.

Thus, the solution to both the problems is not the same. The reduction done in the proof is incorrect.

Therefore, the given proof of CLIQUE-3 being an NP-complete problem does not prove anything.

To prove vertex cover is incorrect

(c)

Consider the information:

The vertex cover problem is one of the NP-complete problems.

The vertex set of the vertex cover problem covers all the edges of the graph.

In other words, it is a vertex subset such that one of the vertices is in the vertex cover for every edge (u,v) in the graph.

Issue with the proof:

The given reduction of VC-3 to CLIQUE-3 leaves the graph unchanged.

But this does not prove that the subset$C\subseteq V$ is a vertex cover if and only if the complementary set V-C is a clique in a graph.

Due to this, the correctness of the reduction cannot be proved.

Because, the problem CLIQUE-3 can be in NP-completeness only if the reduction is true, so it is not NP-complete.

Therefore, the proof using the vertex cover is incorrect.

Algorithm

(d)

Consider the information:

An algorithm is the steps used to solve the problem.

The time taken by the algorithm to solve the problem depending upon the input size is the algorithm’s time complexity.

The objective is to form an algorithm for the problem CLIQUE-3.

Algorithm description:

In the CLIQUE-3 problem, every vertex has a degree at most 3.

This means that all the vertices have at most 3 edges.

It can be concluded that the largest of the clique is in 4 vertices.

Therefore, brute force can be applied to all the possible solutions of the size 4 .

The algorithm recursively checks all the connected nodes via an edge for each node in the graph.

Each search in the algorithm is$O\left(\left|V\right|\right)$ and the maximum possible connected nodes are .

Hence, an algorithm for the CLIQUE-3 runs in$O\left(\left|V\right|\right)$ . And for all nodes, it becomes$O\left({\left|V\right|}^4\right)$ .