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
Brazil

... Inácio Lula da Silva Area - Total  - % waterRanked 5th 8,511,965 km² 0.65% Population  - Total (2000)  - ...

 
 
 
This page was created in 69.8 ms