Book: Introduction to Theories of Computation by Sisper (3rd Edition) Recall The
ID: 3696470 • Letter: B
Question
Book: Introduction to Theories of Computation by Sisper (3rd Edition)
Recall The clique problem (page 296 in the textbook): CLIQUE = {(G, k) | G is an undirected graph with a k-clique} We showed that CLIQUE NP. In fact CLIQUE is NP-Complete (Section 7.5). Consider the following related family of problems, where each problem is parametrized by a fixed constant k: CLlQUE(k) = {(G) | G is an undirected graph with a k-clique} Prove that CLlQUE(k) P. (If your answer includes a TM, it is sufficient to give a high-level description.)Explanation / Answer
consider that undirected graog, triangle shaoe is 3-clique ( k-clique).
Now we are going to prove that clique e p.
Let consider Graoh G(V,E) be a graph set of vertices V and set of edges. Then get all triplets
with these vertices and check all triplets exist in E. For checking this edges present or not
will take O(|E|) time. So total time for 3-clique is O(|V|^3 |E|) which can be found in polynomial time.
So , we can say that clique belongs to P and it can be solved in polynomial time.