NP Problems

Introduction

• Some problems are intractable:

as they grow large, we are unable to solve them in
reasonable time.
• What constitutes reasonable time? Standard working
definition: polynomial time
➢ On an input of size n the worst-case running time is
O(nk) for some constant k
➢ Polynomial time: O(n2), O(n3), O(1), O(n lg n)
➢ Not in polynomial time: O(2n), O(nn), O(n!)
 P and NP

• As mentioned, P is set of problems that can be solved in

polynomial time by a deterministic computer: which means that
at any time during the computation, the next computation step is
uniquely determined.
➢ Every algorithm so far we’ve studied provides polynomial-
time solution.

• NP (nondeterministic polynomial time) is the set of problems

that can be solved in polynomial time by a nondeterministic
computer.
 Nondeterminism
• In a non-deterministic algorithm, there are one or more
possibilities for being the next computation step, and the
algorithm chooses one of them.
• Think of a non-deterministic computer as a computer that
magically “guesses” a solution, then has to verify that it is
correct
➢ If a solution exists, computer always guesses it.
➢ One way to imagine it: a parallel computer that can freely
spawn an infinite number of processes
• Have one processor work on each possible solution
• All processors attempt to verify that their solution works
• If a processor finds it has a working solution
➢ So: NP = problems verifiable in polynomial time
 P and NP

Summary so far:

➢ P = problems that can be solved in polynomial time

➢ NP = problems for which a solution can be verified in
polynomial time
➢ Unknown whether P = NP (most suspect not)
 Reduction

➢ Informally, a problem P can be reduced to another problem Q

if any instance of P can be “easily rephrased” as an instance
of Q, the solution to which provides a solution to the instance
of P
• What do you suppose “easily” means?
• This rephrasing is called transformation
➢ Intuitively: If P reduces to Q, P is “no harder to solve” than Q
 Reducibility

• An example:
➢ P: Given a set of Booleans, is at least one TRUE?
➢ Q: Given a set of integers, is their sum positive?
➢ Transformation: (x1, x2, …, xn) = (y1, y2, …, yn) where
yi = 1 if xi = TRUE, yi = 0 if xi = FALSE
• Another example:
➢ Solving linear equations is reducible to solving
quadratic equations.
 NP-Hard and NP-Complete

• If P is polynomial-time reducible to Q, we denote this P p

Q

• Definition of NP-Hard and NP-Complete:

➢ If all problems R  NP are reducible to P, then P is NP-
Hard
➢ We say P is NP-Complete if P is NP-Hard and P  NP

• If P p Q and P is NP-Complete, Q is also NP- Complete

 NP-Complete Problems

• The NP-Complete problems are an interesting class of

problems whose status is unknown
➢ No polynomial-time algorithm has been discovered for
an NP-Complete problem.
➢ No suprapolynomial lower bound has been proved for
any NP-Complete problem, either

• We call this the P = NP question

➢ The biggest open problem in CS
 NP-Complete Problems

• NP-Complete problems are the “hardest” problems in NP:

➢ If any one NP-Complete problem can be solved in
polynomial time…
➢ …then every NP-Complete problem can be solved in
polynomial time…
➢ …and in fact every problem in NP can be solved in
polynomial time (which would show P = NP)
➢ Thus: solve hamiltonian-cycle in O(n100) time, you’ve
proved that P = NP. Retire rich & famous.
 An NP-Complete Problem:
Hamiltonian Cycles

• An example of an NP-Complete problem:

➢ A hamiltonian cycle of an undirected graph is a simple
cycle that contains every vertex.
➢ The hamiltonian-cycle problem: given a graph G, does
it have a hamiltonian cycle?

➢ Describe a naïve algorithm for solving the hamiltonian-

cycle problem. Running time?
 Coming Up

• Given one NP-Complete problem, we can prove many

interesting problems NP-Complete
➢ Graph coloring (= register allocation)
➢ Hamiltonian cycle
➢ Hamiltonian path
➢ Knapsack problem
➢ Traveling salesman
➢ Job scheduling with penalities
➢ Many, many more
 Why Prove NP-Completeness?

• Though nobody has proven that P != NP, if you prove a

problem NP-Complete, most people accept that it is
probably intractable

• Therefore it can be important to prove that a problem is

NP-Complete
➢ Don’t need to come up with an efficient algorithm
➢ Can instead work on approximation algorithms

David Luebke 13
 Proving NP-Completeness

• What steps do we have to take to prove a problem P is NP-

Complete?
➢ Pick a known NP-Complete problem Q
➢ Reduce Q to P
• Describe a transformation that maps instances of Q
to instances of P, s.t. “yes” for P = “yes” for Q
• Prove the transformation works
• Prove it runs in polynomial time
➢ Oh yeah, prove P  NP (What if you can’t?)

David Luebke 14
 Directed Hamiltonian Cycle 
Undirected Hamiltonian Cycle

• What was the hamiltonian cycle problem again?

• For my next trick, I will reduce the directed hamiltonian
cycle problem to the undirected hamiltonian cycle problem
before your eyes
➢ Which variant am I proving NP-Complete?
• Draw a directed example on the board
➢ What transformation do I need to effect?

David Luebke 15
 Transformation:
Directed  Undirected Ham. Cycle
• Given: Directed Hamiltonian cycle is NP-Complete.

• Transform graph G = (V, E) into G’ = (V’, E’):

➢ Every vertex v in V transforms into 3 vertices
v1, v2, v3 in V’ with edges (v1,v2) and (v2,v3) in E’
➢ Every directed edge (v, w) in E transforms into the
undirected edge (v3, w1) in E’ (draw it)
➢ Can this be implemented in polynomial time?
➢ Argue that a directed hamiltonian cycle in G implies an
undirected hamiltonian cycle in G’
➢ Argue that an undirected hamiltonian cycle in G’
implies a directed hamiltonian cycle in G
David Luebke 16
 Review:
Directed  Undirected Ham. Cycle
• Prove the transformation correct:
➢ If G has directed hamiltonian cycle, G’ will have
undirected cycle (straightforward)
➢ If G’ has an undirected hamiltonian cycle, G will have
a directed hamiltonian cycle
• The three vertices that correspond to a vertex v in G
must be traversed in order v1, v2, v3 or v3, v2, v1,
since v2 cannot be reached from any other vertex in
G’
• Since 1’s are connected to 3’s, the order is the same
for all triples. Assume w.l.o.g. order is v1, v2, v3.
• Then G has a corresponding directed hamiltonian
cycle
David Luebke 17
 Undirected Hamiltonian Cycle

• Thus we can reduce the directed problem to the

undirected problem
• What’s left to prove the undirected hamiltonian
cycle problem NP-Complete?

• Argue that the problem is in NP

David Luebke 18
 Hamiltonian Cycle  TSP

• The well-known Traveling Salesman Problem:

➢ Optimization variant: a salesman must travel to n cities,
visiting each city exactly once and finishing where he
begins. How to minimize travel time?
➢ Model as complete graph with cost c(i,j) to go from city i to
city j

• How would we turn this into a decision problem?

➢ A: ask if  a TSP with cost < k

David Luebke 19
 Hamiltonian Cycle  TSP

• The steps to prove TSP is NP-Complete:

➢ Prove that TSP  NP (Argue this)
➢ Reduce the undirected hamiltonian cycle problem to the
TSP
• So if we had a TSP-solver, we could use it to solve
the hamilitonian cycle problem in polynomial time
• How can we transform an instance of the
hamiltonian cycle problem to an instance of the
TSP?
• Can we do this in polynomial time?

David Luebke 20
 Review: Hamiltonian Cycle  TSP

• To transform ham. cycle problem on graph G = (V,E) to

TSP, create graph G’ = (V,E’):
➢ G’ is a complete graph
➢ Edges in E’ also in E have weight 0
➢ All other edges in E’ have weight 1
➢ TSP: is there a TSP on G’ with weight 0?
• If G has a hamiltonian cycle, G’ has a cycle w/
weight 0
• If G’ has cycle w/ weight 0, every edge of that cycle
has weight 0 and is thus in G. Thus G has a ham.
cycle

David Luebke 21
 The SAT Problem

• One of the first problems to be proved NP-Complete was

satisfiability (SAT):
➢ Given a Boolean expression on n variables, can we
assign values such that the expression is TRUE?
➢ Ex: ((x1 →x2)  ((x1  x3)  x4)) x2
➢ Cook’s Theorem: The satisfiability problem is NP-
Complete
• Note: Argue from first principles, not reduction
• Proof: not here

David Luebke 22
 Conjunctive Normal Form

• Even if the form of the Boolean expression is simplified, the

problem may be NP-Complete
➢ Literal: an occurrence of a Boolean or its negation

➢ A Boolean formula is in conjunctive normal form, or CNF, if

it is an AND of clauses, each of which is an OR of literals
• Ex: (x1  x2)  (x1  x3  x4)  (x5)

➢ 3-CNF: each clause has exactly 3 distinct literals

• Ex: (x1  x2  x3)  (x1  x3  x4)  (x5  x3  x4)
• Notice: true if at least one literal in each clause is true

David Luebke 23
 The 3-CNF Problem

• Satisfiability of Boolean formulas in 3-CNF form (the 3-

CNF Problem) is NP-Complete

• The reason we care about the 3-CNF problem is that it is

relatively easy to reduce to others
➢ Thus by proving 3-CNF NP-Complete we can prove
many seemingly unrelated problems NP-Complete

David Luebke 24
 3-CNF → Clique

• What is a clique of a graph G?

• A: a subset of vertices fully connected to each other, i.e. a
complete subgraph of G
• The clique problem: how large is the maximum-size clique
in a graph?
• Can we turn this into a decision problem?
• A: Yes, we call this the k-clique problem
• Is the k-clique problem within NP?

David Luebke 25
 3-CNF → Clique

• What should the reduction do?

• A: Transform a 3-CNF formula to a graph, for which a k-
clique will exist (for some k) iff the 3-CNF formula is
satisfiable

David Luebke 26
 3-CNF → Clique

• The reduction:
➢ Let B = C1  C2  …  Ck be a 3-CNF formula with k
clauses, each of which has 3 distinct literals
➢ For each clause put a triple of vertices in the graph, one
for each literal
➢ Put an edge between two vertices if they are in different
triples and their literals are consistent, meaning not
each other’s negation
➢ Run an example:
B = (x  y  z)  (x  y  z )  (x  y  z )

David Luebke 27
 3-CNF → Clique

• Prove the reduction works:

➢ If B has a satisfying assignment, then each clause has at
least one literal (vertex) that evaluates to 1
➢ Picking one such “true” literal from each clause gives a
set V’ of k vertices. V’ is a clique (Why?)
➢ If G has a clique V’ of size k, it must contain one vertex
in each triple (clause) (Why?)
➢ We can assign 1 to each literal corresponding with a
vertex in V’, without fear of contradiction

David Luebke 28
 Clique → Vertex Cover

• A vertex cover for a graph G is a set of vertices incident to

every edge in G
• The vertex cover problem: what is the minimum size
vertex cover in G?
• Restated as a decision problem: does a vertex cover of size
k exist in G?
• vertex cover is NP-Complete

David Luebke 29
 Clique → Vertex Cover

• First, show vertex cover in NP (How?)

• Next, reduce k-clique to vertex cover
➢ The complement GC of a graph G contains exactly those
edges not in G
➢ Compute GC in polynomial time
➢ G has a clique of size k iff GC has a vertex cover of size
|V| - k

David Luebke 30
 Clique → Vertex Cover

• Claim: If G has a clique of size k, GC has a vertex cover of

size |V| - k
➢ Let V’ be the k-clique
➢ Then V - V’ is a vertex cover in GC
• Let (u,v) be any edge in GC
• Then u and v cannot both be in V’ (Why?)
• Thus at least one of u or v is in V-V’ (why?), so
edge (u, v) is covered by V-V’
• Since true for any edge in GC, V-V’ is a vertex cover

David Luebke 31
 Clique → Vertex Cover

• Claim: If GC has a vertex cover V’  V, with |V’| = |V| - k,

then G has a clique of size k
➢ For all u,v  V, if (u,v)  GC then u  V’ or
v  V’ or both (Why?)
➢ Contrapositive: if u  V’ and v  V’, then
(u,v)  E
➢ In other words, all vertices in V-V’ are connected by an
edge, thus V-V’ is a clique
➢ Since |V| - |V’| = k, the size of the clique is k

David Luebke 32
 General Comments

• Literally hundreds of problems have been shown to be NP-

Complete

• Some reductions are profound, some are comparatively

easy, many are easy once the key insight is given

• You can expect a simple NP-Completeness proof on the

final

David Luebke 33
 Other NP-Complete Problems

• Subset-sum: Given a set of integers, does

there exist a subset that adds up to some
target T?
• 0-1 knapsack: when weights not just
integers
• Hamiltonian path: Obvious
• Graph coloring: can a given graph be
colored with k colors such that no adjacent
vertices
David Luebke
are the same color? 34
The End