CSC5160
Topics in Algorithms
Tutorial 2
Introduction to NP-Complete Problems
Feb 8 2007
Jerry Le
[email protected]
Outline
• General definitions
- P, NP, NP-hard, NP-easy, and NP-complete...
- Polynomial-time reduction
• Examples of NP-complete problems
General Definitions
P, NP, NP-hard, NP-easy, and NP-complete
• Problems
- Decision problems (yes/no)
- Optimization problems (solution with best score)
• P
- Decision problems (decision problems) that can be solved in
polynomial time
- can be solved “efficiently”
• NP
- Decision problems whose “YES” answer can be verified in
polynomial time, if we already have the proof (or witness)
• co-NP
- Decision problems whose “NO” answer can be verified in
polynomial time, if we already have the proof (or witness)
General Definitions
P, NP, NP-hard, NP-easy, and NP-complete
• e.g. The satisfiability problem (SAT)
- Given a boolean formula
( x1 ∨ x2 ∨ x3 ∨ x4 ) ∧ ( x5 ∨ x6 ∨ x7 ) ∧ x8 ∧ x9
is it possible to assign the input x1...x9, so that the formula
evaluates to TRUE?
- If the answer is YES with a proof (i.e. an assignment of input
value), then we can check the proof in polynomial time (SAT is
in NP)
- We may not be able to check the NO answer in polynomial
time (Nobody really knows.)
General Definitions
P, NP, NP-hard, NP-easy, and NP-complete
• NP-hard
- A problem is NP-hard iff an polynomial-time algorithm for it
implies a polynomial-time algorithm for every problem in NP
- NP-hard problems are at least as hard as NP problems
• NP-complete
- A problem is NP-complete if it is NP-hard, and is an element of
NP (NP-easy)
Cook’s Theorem
SAT is NP-hard
we knew
SAT is in NP
SAT is NP-complete
General Definitions
P, NP, NP-hard, NP-easy, and NP-complete
• Relationship between decision problems and
optimization problems
- every optimization problem has a corresponding
decision problem
- optimization: minimize x, subject to constraints
- yes/no: is there a solution, such that x is less than
c?
- an optimization problem is NP-hard (NP-complete)
if its corresponding decision problem is NP-hard (NP-
complete)
General Definitions
Polynomial-time reductions
• How to know another problem, A, is NP-complete?
- To prove that A is NP-complete, reduce a known
NP-complete problem to A
reduction in P(n) solve A
SAT A YES/NO
• Requirement for Reduction
- Polynomial time
- YES to A also implies YES to SAT, while
NO to A also implies No to SAT (Note that A must
also have short proof for YES answer)
General Definitions
Polynomial-time reductions
• An example of reduction
- 3CNF clause
( a ∨ b ∨ c) ∧ ( b ∨ c ∨ d ) ∧ (a ∨ c ∨ d )
literal
- 3SAT: is a boolean formula in 3CNF has a feasible
assignment of inputs so that it evaluates to TRUE?
- reduction from 3SAT to SAT (3SAT is NP-complete)
change into 3CNF solve 3SAT
SAT (in polynomial time, 3SAT YES/NO
without changing function value)
Outline
• General definitions
• Examples of NP-complete problems
- Vertex cover
- Independent set
- Set cover
- Steiner tree
...
Examples of NP-complete problems
Vertex cover
• Vertex cover
- given a graph G=(V,E), find the smallest number of
vertexes that cover each edge
- Decision problem: is the graph has a vertex cover of
size K?
- reduction:
3SAT with O(n)
n variables and c clauses A constructive graph G
does G has a vertex cover
of size n+2c?
YES/NO
Examples of NP-complete problems
Vertex cover
• Vertex cover
- an example of the constructive graph
clause
( a ∨ b ∨ c) ∧ ( b ∨ c ∨ d ) ∧ (a ∨ c ∨ d )
variable literal
gadget
a a b b c c d d
a b a
clause
gadget
b c c d c d
Examples of NP-complete problems
Vertex cover
• Vertex cover
- we must prove:
the graph has a n+2c vertex cover, if and only if the 3SAT is
satisfiable (to make the two problem has the same YES/NO answer!)
variable
gadget
a a b b c c d d
a b a
clause
gadget
b c c d c d
Examples of NP-complete problems
Vertex cover
• Vertex cover
- if the graph has a n+2c vertex cover
1) there must be 1 vertex per variable gadget, and 2 per clause gadget
2) in each clause gadget, set the remaining one literal to be true
variable
gadget
a a b b c c d d
a b a
clause
gadget
b c c d c d
Examples of NP-complete problems
Vertex cover
• Vertex cover
- if the 3SAT is satisfiable
1) choose the TURE literal in each variable gadget
2) choose the remaining two literal in each clause gadget
we are done
variable
gadget
a a b b c c d d
a b a
clause
gadget
b c c d c d
Examples of NP-complete problems
Independent set
• Independent set
- independent set: a set of vertices in the graph with
no edges between each pair of nodes.
- given a graph G=(V,E), find the largest independent
set
- reduction from vertex cover:
largest independent set
smallest vertex cover S
V/S
Examples of NP-complete problems
Independent set
• Independent set
- if G has a vertex cover S, then V/S is an independent set
proof: consider two nodes in V/S:
if there is an edge connecting them, then one of them
must be in S, which means one of them is not in V/S
- if G has an independent set I, then V/I is a vertex cover
proof: consider one edge in G:
if it is not covered by any node in V/I, then its two end
vertices must be both in I, which means I is not an independent
set
Examples of NP-complete problems
Set cover
• Set cover
- given a universal set U, and several subsets S1,...Sn
- find the least number of subsets that contains each
elements in the universal set
- vertex cover is a special case of set cover:
1) the universal set contains all the edges
2) each vertex corresponds to a subset, containing
the edges it covers
Vertex cover trivial Set cover
Examples of NP-complete problems
Steiner tree
• Steiner tree
- given a graph G=(V,E), and a subset C of V
- find the minimum tree to connect each vertex in C
- reduction
Vertex cover for Graph G Steiner tree for graph G’
vertex
(u,v) edge
(u,v)-v
edge
(u,v)-u
G’
G
(only edges
with
distance 1
are shown)
Examples of NP-complete problems
Steiner tree
• Steiner tree
- G’ is a complete graph
- for every node u in G, creat a node u in G’
- for every edge (u,v) in G, create a node (u,v) in G’
- in G’, every node (u,v) is connected to u and v with distance 1
- in G’, every node u and v is connected with distance 1
- other edges in G’ are of distance 2 vertex
(u,v) edge
(u,v)-v
edge
(u,v)-u
G’
G
(only edges
with
distance 1
are shown)
Examples of NP-complete problems
Steiner tree
• Steiner tree
- in the Steiner tree problem for G’, choose C to be the set of all
nodes (u,v)
- G’ has a minimum Steiner tree of cose m+k-1 iff G has a
minimum vertex cover of size k
vertex
(u,v) edge
(u,v)-v
edge
(u,v)-u
G’
G
(only edges
with
distance 1
are shown)
Examples of NP-complete problems
Summary of some NPc problems
SAT
3SAT
Maximum cut
Graph coloring Vertex cover
Independent Set Maximum Minimum Hamiltonian
set cover clique size Steiner tree cycle
find more NP-complete problems in
http://en.wikipedia.org/wiki/List_of_NP-complete_problems
Acknowledgement
Some materials in these slides are from
Dr. Jeff Erickson’s Lecture notes:
http://compgeom.cs.uiuc.edu/~jeffe/teaching/
algorithms/notes/21-nphard.pdf,
which are the most intuitive and interesting lecture notes
on NP-hardness I have ever seen.
