Question

I claim that in most situations if you can solve the decision problem in polynomial time then you can solve the optimization problem in polynomial time. Prove that this is true for the CLIQUE problem.

Answer 1

Yes CLIQUE has decision problem as

Input: G (V.E.) and number k

Output : There is set of vertices in U and edge in E

The clique decision problem is NP - complete where clique is a fixed parameter and hard to approximate. In clique, all maximal clique listed.

Step-by-step explanation:

In the computer, the CLIQUE is the computational problem of finding the cliques in subsets of vertices, all sides in a graph. It depending on cliques in which information should be found.

A clique has an edge in connecting the vertices; An edge connects only two vertices. For example, if you want to connect two vertices, then two edges need if you want three, then three edges need.

The clique problem is finding the clique in adjacent to each other in a graph. Its decision problem is NP-complete.

In computer science, a decision problem is a problem that posed yes or no of the input values. In computational and computability theory. it is a method used for solving a decision problem that is called the decision procedure of the problem.