The decision clique problem asks whether a given finite graph contains a clique with at least vertices, where is part of the input. A proposed clique can be checked by testing all pairs of its vertices for adjacency. The problem is NP-complete; the optimization version asks for a largest clique.
Taking a complement graph turns a clique into an independent set, so clique search and maximum-independent-set search encode the same combinatorial obstruction. For fixed , checking all -vertex subsets takes polynomial time in the graph size, but its exponent depends on . This does not give a polynomial-time algorithm when varies with the input.
Given an explicitly represented finite simple graph and a nonnegative integer , decide whether contains a clique of size . The problem is NP-complete. A polynomial-time many-one reduction from SAT first obtains conjunctive normal form by a Tseitin transformation, makes one vertex per Boolean literal occurrence, and joins noncontradictory occurrences from different Boolean clauses. A clique as large as the Boolean clause count is equivalent to a satisfying assignment.

Articles by others on the same topic (1)

The Clique problem is a well-known problem in graph theory and computer science, particularly within the field of computational complexity. A clique in a graph is defined as a subset of vertices such that every two distinct vertices in the subset are adjacent, which means there is an edge connecting every pair of vertices in that subset.