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
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.