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
David McReynolds

... in 1960 joined the War Resisters League (WRL), which he would remain a member until his retirement in 1999 (he remains active within the nonviolence movement and regularly ...

 
 
 
This page was created in 31.5 ms