NP-Completeness & Reductions

CS F364 — Design & Analysis of Algorithms | Summer 2026

P, NP, NP-completeness, polynomial-time reductions, 3-SAT to CLIQUE, CLIQUE to Vertex Cover, designing new reductions

← Practice

NoteProblem F1

True or false? Justify briefly.

  1. If A \le_P B and B is in P, then A is in P.
  2. If A \le_P B and A is NP-complete, then B is NP-complete.
  3. If P \neq NP, then no NP-complete problem can be solved in polynomial time.
  1. True. Polynomial-time reduction + polynomial algorithm for B gives polynomial algorithm for A.
  2. False. Need also B \in \text{NP}. If B is outside NP, the reduction shows NP-hardness, not NP-completeness.
  3. True. If any NP-complete problem is in P, then all NP problems are in P (by reduction), so P = NP.
NoteProblem F2

What are the two things you must prove to show a problem B is NP-complete? Suppose you already know that 3-SAT is NP-complete. Is constructing a reduction from 3-SAT to B sufficient?

Prove (1) B \in \text{NP}, and (2) B is NP-hard (via reduction from a known NP-complete problem A). A reduction from 3-SAT to B gives NP-hardness, but B must also be in NP for completeness.

NoteProblem F3

Reduce 3-SAT to CLIQUE for the formula:

\phi = (x_1 \lor x_2 \lor x_3) \land (\bar{x}_1 \lor \bar{x}_2 \lor x_3) \land (x_1 \lor \bar{x}_2 \lor \bar{x}_3)

  1. Show the constructed graph G and the target clique size k.
  2. Find a satisfying assignment and the corresponding k-clique in G.
  3. Show that if G has a k-clique, then \phi is satisfiable.
  1. Three clauses \to 9 vertices. Groups: G_1=\{x_1,x_2,x_3\}, G_2=\{\bar{x}_1,\bar{x}_2,x_3\}, G_3=\{x_1,\bar{x}_2,\bar{x}_3\}. Edges connect all pairs across different groups except conflicting literals (x_i and \bar{x}_i). k = 3.
Clause 1 Clause 2 Clause 3 x₁ x₂ x₃ ¬x₁ ¬x₂ x₃ x₁ ¬x₂ ¬x₃

Conflicting pairs (no edge): (x_1,\bar{x}_1), (x_2,\bar{x}_2), (x_3,\bar{x}_3) within and across groups. Within each group there are no edges (clique picks at most one per clause).

  1. Satisfying assignment: x_1=T, x_2=F, x_3=T. True literals: x_1 (C1), \bar{x}_2 (C2), x_1 (C3). These 3 vertices form a 3-clique in G.

  2. A k-clique must pick one vertex per clause (no edges within a group). No conflicting pair means no x and \bar{x} both picked. Setting picked literals to true gives a consistent satisfying assignment.

NoteProblem F4

Reduce CLIQUE to Vertex Cover for the graph G below with k=3.

G 1 2 3 4 5 6
  1. Construct the complement graph \bar{G} and compute k' = |V| - k.
  2. Find a 3-clique in G and the corresponding vertex cover in \bar{G}.
  3. Explain why the duality holds: S is a clique in G \iff V \setminus S is a vertex cover in \bar{G}.
G 3-clique 1 2 3 4 5 6 G vertex cover 1 2 3 4 5 6

  1. G has edges: (1,2),(1,3),(2,3),(3,4),(4,5),(4,6),(5,6). \bar{G} has all non-edges of G: (1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,5),(3,6). k' = |V| - k = 6 - 3 = 3.

  2. A 3-clique in G: \{1,2,3\} (highlighted red). The complement vertex cover in \bar{G}: \{4,5,6\} (highlighted green). Every edge of \bar{G} is incident to at least one of \{4,5,6\}.

  3. Proof: If S is a clique in G, then no edge of \bar{G} connects two vertices of S. So every edge of \bar{G} has at least one endpoint in V\setminus S, making V\setminus S a vertex cover in \bar{G}. Conversely, if V\setminus S is a vertex cover in \bar{G}, then no edge of \bar{G} is entirely within S, so S is a clique in G.

NoteProblem F5

Independent Set (IS): Given graph G=(V,E) and integer k, does G contain a set I \subseteq V of size k with no edges between any pair in I? Give a direct reduction from CLIQUE to Independent Set. (Hint: think about graph complements.)

Reduction: CLIQUE instance (G,k) \to IS instance (\bar{G}, k). Since a clique in G is an independent set in \bar{G}, we have: G has a k-clique \iff \bar{G} has an independent set of size k. This is a direct polynomial-time reduction.