A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The clique problem asks whether a graph contains a subset of k vertices all pairwise adjacent (a complete subgraph). NP-completeness of the clique problem follows from reduction from 3-SAT. Its complement, the independent set problem, is also NP-complete, illustrating how graph optimization problems naturally exhibit computational hardness.
A clique in a graph is a set of vertices that are all mutually connected — every pair has an edge between them. The clique decision problem CLIQUE asks: given a graph G and integer k, does G contain a clique of size k? This seems like a search problem over vertex subsets, and while checking a candidate clique is easy (inspect all k(k−1)/2 pairs), finding one requires searching exponentially many subsets in the worst case. Your prerequisite work with NP-completeness gives you the tools to explain why no polynomial algorithm is known.
To prove CLIQUE is NP-complete, you reduce from 3-SAT — the problem you already know is NP-complete. Given a 3-CNF formula with m clauses C₁, C₂, …, Cₘ, construct a graph as follows: create one vertex for each literal in each clause (so up to 3m vertices total, labeled by their (literal, clause) pair), then connect two vertices with an edge if and only if they come from *different* clauses and are *not* contradictory (i.e., not a literal and its negation). Now set k = m. The key insight is that a satisfying assignment to the formula corresponds exactly to choosing one true literal per clause, and those m chosen literals form a clique — they're all from different clauses and no two are contradictory (a satisfying assignment never makes both x and ¬x true). Conversely, any k-clique must pick exactly one vertex per clause and can never pick complementary literals, so it defines a consistent partial assignment that satisfies every clause. The reduction runs in polynomial time, so CLIQUE is NP-hard; it's also in NP (a clique certificate can be verified in polynomial time), hence NP-complete.
The independent set problem — does G contain a set of k vertices with *no* edges between them? — is the complement in a precise sense: a set S is a clique in G if and only if S is an independent set in the complement graph Ḡ (which has an edge where G doesn't). This means CLIQUE and INDEPENDENT SET are polynomial-time equivalent, and since CLIQUE is NP-complete, so is INDEPENDENT SET. Similarly, VERTEX COVER (find a set of k vertices touching every edge) is NP-complete and connects to independent set via the complement: S is an independent set if and only if V \ S is a vertex cover. These three problems form a tightly linked family, all capturing the same underlying computational hardness from different angles.
The pattern generalizes: many natural graph optimization problems — maximum clique, maximum independent set, minimum vertex cover — are NP-hard even to approximate within constant factors. This is not merely about exact computation; it reflects deep structure in how combinatorial optimization interacts with constraint satisfaction. The polynomial reduction framework you learned with 3-SAT is the workhorse that connects all these problems into a single web of hardness, where solving any one efficiently would collapse the entire NP-complete class to P.