Encyclopedia > Clique problem

  Article Content

Clique problem

In computer science, the Clique Problem is an NP-complete problem in complexity theory.

A clique (pronounced "click") in a graph is a set of pairwise adjacent vertices. In the example graph in Graph theory, vertices 1, 2 and 5 form a clique.

The clique problem is the optimization problem of finding a clique of maximum size in a graph. The problem is a decision problem, so we wonder in a clique of size k exists in the graph.

CLIQUE = {<G,K>| G is a graph with clique, size k}

A brute force algorithm to find a clique in a graph is to list all subsets of vertices, V and check each one to see if it forms a clique. The algorithm is polynomial if k is constant, but super-duper polynomial time if k is |V|/2.

Proof

  • TODO



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Lake Ronkonkoma, New York

... 65 years of age or older. The average household size is 2.86 and the average family size is 3.32. In the town the population is spread out with 24.7% under the age of 18, ...

 
 
 
This page was created in 32.9 ms