Lecture 25

More NP-completeness

CSE 421 Autumn 2025

1

Previously…

2

-completeness

Definition: A problem is -complete if �(a) �(b) For every problem , it holds that

3

Condition (b) on its own is known as “-hardness”.

The “first” -complete problem

Satisfiability

Theorem: Satisfiability is -complete.

4

Input: , the description of a polynomial-time algorithm and integer in unary.

Output: Whether there exists a such that and .

Proof: Two lectures ago.

3-SAT is NP-complete

5

Theorem: 3-SAT is -complete.

Input: A 3-CNF formula .

Output: “yes” if there exists a such that . “No” otherwise.

Proof: Last lecture.

Today

6

• NP-completeness of Vertex Cover and 3-coloring

Vertex Cover is -complete

• Vertex Cover is in (the proof is the set of vertices itself).
• We will show that 3-SAT Vertex Cover. And so Vertex Cover is -complete

Our task: given an instance of 3-SAT, find a way to map it to a vertex cover instance in a way that preserves “yes” and “no” instances.

Vertex Cover (decision version): On input a graph and an integer , decide if there exists a vertex cover of size (that is, a subset of vertices of size that touches every edge).

Vertex Cover is -complete

The construction:

• contains 3 vertices per clause, one for each literal. Set , where is the number of clauses in .
• Add an edge between each pair of variables in the same clause.
• Add edges connecting each variable to its negation.

Our task: given an instance of 3-SAT, find a way to map it to a vertex cover instance in a way that preserves “yes” and “no” instances.

Vertex Cover is -complete

The construction:

• contains 3 vertices per clause, one for each literal. Set , where is the number of clauses in .
• Add an edge between each pair of variables in the same clause.
• Add edges connecting each variable to its negation.

Our task: given an instance of 3-SAT, find a way to map it to a vertex cover instance in a way that preserves “yes” and “no” instances.

Assume without loss of generality that each clause has exactly 3 literals (can always duplicate a literal without changing whether is “yes” or “no” instance)

Vertex Cover is -complete

10

Vertex Cover is -complete

Theorem: is satisfiable iff has a vertex cover of size.

Proof:

• “Yes” “Yes”: If is satisfiable, let be a satisfying assignment.
• For each clause, pick one of the variables that must be set to true, and include the other two in the vertex cover.

11

Vertex Cover is -complete

Theorem: is satisfiable iff has a vertex cover of size.

Proof:

• “Yes” “Yes”: If is satisfiable, let be a satisfying assignment.
• For each clause, pick one of the variables that must be set to true, and include the other two in the vertex cover. Claim: This is a vertex cover of size . Why?
• Is every “triangle” edge covered?

12

Vertex Cover is -complete

Theorem: is satisfiable iff has a vertex cover of size.

Proof:

• “Yes” “Yes”: If is satisfiable, let be a satisfying assignment.
• For each clause, pick one of the variables that must be set to true, and include the other two in the vertex cover. Claim: This is a vertex cover of size . Why?
• Each “triangle” edge is covered since 2 vertices are selected per triangle.
• Is every negation edge covered?

13

Vertex Cover is -complete

Theorem: is satisfiable iff has a vertex cover of size.

Proof:

• “Yes” “Yes”: If is satisfiable, let be a satisfying assignment.
• For each clause, pick one of the variables that must be set to true, and include the other two in the vertex cover. Claim: This is a vertex cover of size . Why?
• Each “triangle” edge is covered since 2 vertices are selected per triangle.
• Each “negation” edge is covered since not selecting both endpoints would mean both and are true in the satisfying assignment.

14

Vertex Cover is -complete

Theorem: is satisfiable iff has a vertex cover of size.

Proof:

• “Yes” “Yes”:

15

Vertex Cover is -complete

Theorem: is satisfiable iff has a vertex cover of size.

Proof:

• “Yes” “Yes”: If has a vertex cover of size , then by previous lemma, the vertex cover is exactly of size since we need to select at least two vertices per triangle.
• Set the excluded variable in each triangle to be true (this makes every OR clause evaluate to 1)
• Do we ever set a variable and its negation to both be true?

16

Vertex Cover is -complete

Theorem: is satisfiable iff has a vertex cover of size.

Proof:

• “Yes” “Yes”: If has a vertex cover of size , then by previous lemma, the vertex cover is exactly of size since we need to select at least two vertices per triangle.
• Set the excluded variable in each triangle to be true (this makes every OR clause evaluate to 1)
• Since each “negation edge” is covered (because we are considering a vertex cover), the assignment will set at most one of and to be true (so this is a valid assignment).

17

3-coloring is -complete

• 3-Coloring as the proof is the assignment itself.
• We will show that 3-SAT 3-Coloring
• We will have to create a graph representing a formula
• Some “part” of the graph will have to represent variables and their negations (and enforce that that they cannot both be true)
• Some “part” of the graph will have to represent clauses such that the “part” is correctly colored iff the clause evaluates to true.
• A great example that proving NP-completeness can sometimes be quite sophisticated (and fun).

18

Input: a graph . �Output: whether there exists an assignment such that for every edge .

3-coloring is -complete

19

Goal: Map a 3-SAT formula to a graph that preserves “yes” and “no” instances

The approach:

We will develop two “gadgets”:

1. The first will enforce that, for a valid coloring, exactly one of and must be colored Green, and the other Red.
2. The second will enforce that, for a valid coloring at least one literal in each clause must be colored Green.

Let’s start by creating, for each variable , vertices labelled and

We will eventually interpret a vertex being Green as the corresponding literal being set to true.

3-coloring is -complete

• Add one auxiliary vertex. Without loss of generality, let’s always take the color assigned to it to be Blue.
• Add edges from to each and .

20

The 1st “gadget”

3-coloring is -complete

• Add one auxiliary vertex. Without loss of generality, let’s always take the color assigned to it to be Blue.
• Add edges from to each and . This enforces that exactly one of and must be colored Green and the other Red.
• Note: so far the valid colorings are in bijection with assignments of the variables to true or false.

21

The 1st “gadget”

3-coloring is -complete

• Add one auxiliary vertex. Without loss of generality, let’s always take the color assigned to it to be Blue.
• Add edges from to each and . This enforces that exactly one of and must be colored Green and the other Red.
• Note: so far the valid colorings are in bijection with assignments of the variables to true or false.
• Add two more auxiliary vertices, which we call T and F. Let’s define Green to be the color assigned to T and Red the color assigned to F.

22

The 1st “gadget”

3-coloring is -complete

• Add one auxiliary vertex. Without loss of generality, let’s always take the color assigned to it to be Blue.
• Add edges from to each and . This enforces that exactly one of and must be colored Green and the other Red.
• Note: so far the valid colorings are in bijection with assignments of the variables to true or false.
• Add two more auxiliary vertices, which we call T and F. Let’s define Green to be the color assigned to T and Red the color assigned to F.

23

The 1st “gadget”

3-coloring is -complete

The 2nd “gadget”

3-coloring is -complete

The 2nd “gadget”

25

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

Totally unclear if such a graph exists..

3-coloring is -complete

The 2nd “gadget”

26

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

The same vertex T as before

The same vertex F as before

It turns out that this tricky little graph does the job..

The graph includes the vertices�, T, F, and possibly more�auxiliary vertices that we create

3-coloring is -complete

27

The 2nd “gadget”

The same vertex T as before

The same vertex F as before

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

It turns out that this tricky little graph does the job..

Recall that every literal must be colored Red or Green by the 1st gadget!�(not pictured here, but �are involved in the 1st gadget)�

3-coloring is -complete

28

The 2nd “gadget”

The same vertex T as before

The same vertex F as before

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

It turns out that this tricky little graph does the job..

3-coloring is -complete

29

The 2nd “gadget”

The same vertex T as before

The same vertex F as before

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

It turns out that this tricky little graph does the job..

3-coloring is -complete

30

The 2nd “gadget”

The same vertex T as before

The same vertex F as before

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

It turns out that this tricky little graph does the job..

3-coloring is -complete

31

The 2nd “gadget”

The same vertex T as before

The same vertex F as before

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

It turns out that this tricky little graph does the job..

3-coloring is -complete

32

The 2nd “gadget”

The same vertex T as before

The same vertex F as before

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

It turns out that this tricky little graph does the job..

3-coloring is -complete

33

The 2nd “gadget”

The same vertex T as before

The same vertex F as before

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

It turns out that this tricky little graph does the job..

3-coloring is -complete

34

The 2nd “gadget”

The same vertex T as before

The same vertex F as before

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

It turns out that this tricky little graph does the job..

3-coloring is -complete

35

The 2nd “gadget”

The same vertex T as before

The same vertex F as before

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

It turns out that this tricky little graph does the job..

3-coloring is -complete

36

The 2nd “gadget”

The same vertex T as before

The same vertex F as before

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

It turns out that this tricky little graph does the job..

3-coloring is -complete

37

The 2nd “gadget”

The same vertex T as before

The same vertex F as before

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

It turns out that this tricky little graph does the job..

3-coloring is -complete

38

The 2nd “gadget”

The same vertex T as before

The same vertex F as before

We now construct a “gadget” that maps a clause to a graph such that:�it can be colored (validly) iff at least one of vertices is colored Green.��

It turns out that this tricky little graph does the job..

3-coloring is -complete

Full construction:

• Construct triangles (,,) and for each variable (1st “gadget”)
• For each clause , construct the 2nd “gadget” using vertices (and creating the required auxiliary vertices and edges)

39

Putting it all together

3-coloring is -complete

Putting it all together

Proof that the reduction works:

• “Yes” “Yes”: Let be a satisfying assignment to .
• Color the vertices Green, Red, and Blue.
• Color the vertices of and Green or Red: the vertex corresponding to true should be set to Green and the other to Red.
• Since every clause is satisfied, one of the literals in each clause will be Green, and so there exists an assignment of colors for each “clause gadget” (by our previous case analysis).
• “Yes” “Yes”: Call Green, Red, and Blue the colors assigned to , , and .
• Set if assigned color Green and if assigned color Red (it will never be assigned Blue due to the constraints from the 1st gadget)
• Since the gadget for each clause has a valid coloring, at least one of the 3 literals must be Green (by our previous case analysis), so each clause is satisfied.

40