Complexity Classes Are Terrifying

• But like also ... really really cool
• Hidden within complexity classes lies some philosophical questions
• Will try to talk more about it at the end

Advice When Proving NP-Completeness

• Take the problem you are trying to prove is NP-Complete
• Assume you have a solution to this unknown problem
• Convert an instance of the known NP-Complete problem to the assumed solution
• Show solving the unknown problem gives a solution to the known NP-Complete
• Use the unknown to solve the known!!!

Vertex Cover

Given a graph and integer , determine if there is some subset of the vertices such that each edge is incident to some vertex in

Vertex Cover: Example

Vertex Cover: Example

Use Vertex Cover to Solve Independent Set

• If we can solve the vertex cover problem ...
  • We can solve independent set too!
• So how does getting the vertex cover help us?
  • Each vertex in the vertex cover is adjacent to every vertex
  • What about the vertices not in the vertex cover, i.e. the compliment?

General Algorithm

def IndependentSet(G, k):
    return VertexCover(G, n - k)

Some Precision

• We need to prove two things:
  • If it finds a solution, then the solution is correct
  • If a solution exists, then our algorithm finds it
• For our problem, that means:
  • The compliment of the vertex cover is an independent set
  • If an independent set of size exists, then a vertex cover of size also exists

Proving the First Statement

The compliment of the vertex cover is an independent set

• Suppose the statement is false
• Two vertices not in the vertex cover are adjacent
• Is that edge covered in the vertex cover?
• Contradiction!

Proving the Second Statement

If an independent set of size exists, then a vertex cover of size also exists

• Show that an independent set of size means there is a vertex cover of size
• Conveniently, just proving the reverse of the first statement!

Proving the Second Statement

The compliment of the independent set is a vertex cover

• Suppose the statement is false
• There is an edge that is not covered by the compliment
• Means both vertices on the edge are in the independent set
• But that makes them not independent anymore?
• Contradiction!

Set Cover Problem

We are given a series of sets and a value , can you select no more than sets such that every element in the sets is in at least one element of the chosen?

Set Cover

Set Cover

Use Set Cover to Solve Vertex Cover

• Solution is extremely natural!
• Each vertex is a set
• Each edge is an element of the set
• The set numbers chosen are the vertices we choose!