The Clique reference article from the English Wikipedia on 24-Apr-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Clique

In graph theory, a clique in a undirected graph G, is a set of vertices V' such that for every two vertices in V, there exists an edge connecting the two. Additionally, this means that a clique is simply a complete subrgraph of G. The size of a clique is the number of vertices it contains.

The clique problem refers to the problem of finding the largest clique in any graph G. This problem is NP-complete, and as such, many consider that it is unlikely that an efficient algorithm for finding the largest clique of a graph exists.

The opposite of a clique is an independent set. If we already know that the independent set problem is NP-complete, then it is easy to prove, as the size of the largest clique is the same as the size of the largest independent set in the inverse graph.

This is the "Clique" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.