A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Vertex cover asks: given a graph and integer k, does a set of k vertices exist such that every edge touches at least one? Clique asks: does the graph contain a complete subgraph of size k? Both are NP-complete. Clique and independent set are complementary: finding a clique in G equals finding an independent set in the complement graph. These problems exemplify how different-seeming combinatorial problems connect via polynomial reductions, sharing fundamental hardness despite surface dissimilarity.
You already know that SAT is NP-complete and that polynomial-time reductions let you prove new problems NP-complete by transforming known hard problems into them. Vertex Cover and Clique are two of the most important problems in the NP-complete ecosystem, and understanding how they relate to each other — and to SAT — illustrates how a single thread of hardness weaves through seemingly unrelated combinatorial questions.
Vertex Cover asks: can you select at most k vertices from a graph such that every edge has at least one of its endpoints in your selected set? Think of it as placing guards in a museum hallway network — you want every hallway (edge) monitored by at least one guard (vertex), using as few guards as possible. Clique asks the opposite kind of question: does the graph contain a group of k vertices that are all mutually connected? Think of it as finding a group of k people at a party where everyone in the group knows everyone else. Despite their different flavors — one is about covering structure, the other about finding dense structure — both are NP-complete.
The connection between these problems runs through a third problem: Independent Set. An independent set is a group of vertices with no edges between them — the exact opposite of a clique. Here is the key insight: a set S is a clique in graph G if and only if S is an independent set in the complement graph Ḡ (which has an edge wherever G does not, and vice versa). Furthermore, a set S is a vertex cover in G if and only if V − S (the remaining vertices) is an independent set in G. This gives you a chain: Clique in G ↔ Independent Set in Ḡ ↔ Vertex Cover in Ḡ. Since complement construction is a polynomial-time operation, NP-completeness transfers freely along this chain. Proving any one of these three problems NP-complete immediately gives you the other two.
The original NP-completeness proof for Vertex Cover typically reduces from 3-SAT. Each clause becomes a small gadget in the graph, and the structure ensures that choosing a vertex cover of size k corresponds to finding a satisfying assignment. The reduction for Clique often goes through Independent Set. What makes these problems especially important beyond theory is that they model real optimization scenarios — network reliability (vertex cover), social network analysis (clique detection), and wireless channel assignment (independent set). The NP-completeness results explain why these practical problems resist efficient exact solutions, motivating the study of approximation algorithms. Notably, Vertex Cover has a simple 2-approximation (greedily pick both endpoints of uncovered edges), while Clique has no known constant-factor approximation — showing that NP-complete problems, despite sharing worst-case hardness, can differ dramatically in how well they can be approximately solved.