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
Father Damien

... On May 10, 1873, at his request, he was permitted to travel to Molokai to help the lepers who had virtually nothing to keep them warm or fed. After twelve years of ...

 
 
 
This page was created in 23.6 ms