Design and Analysis of Algorithm
School of Computer Engineering
KALINGA INSTITUTE OF INDUSTRIAL TECHNOLOGY
NP Completeness
Biswajit Sahoo, KIIT
Contents of Discussion
2
Intractabe Problem
Nondeterministic Algorithm
P and NP Defination
Optimization & Decision Problem
Verification of Problem
Reducibility
NP Complete & NP Hard Defination
Cook’s Theorem
Examples of NP Complete
Clique Decision Problem
Hamiltonian Cycle, TSP
Sum of Subset, Graph Coloring
Biswajit Sahoo, KIIT
Tractability
3
Tractable problems: Intractable problems:
Polynomial time Super Polynomial time
O(n2), O(n3), O(1),O(nlg n) O(2n), O(n 2n), O(nn),
O(n!)
Ex:- O(n3); for n=100 Ex:- O(2n); for n=100
Number of steps = Number of steps
10,00,000 ≈90,....,00
Biswajit Sahoo, KIIT
Prove
Tractability
4
Tractable problems: Intractable problems:
Polynomial time Super Polynomial time
O(n2), O(n3), O(1),O(nlg n) O(2n), O(n 2n), O(nn),
O(n!)
Ex:- O(n100); for n=10 Ex:- O(2n); for n=10
Number of steps ≈ Number of steps = 1024
10,...,000 Intractable ?
Tractable
Biswajit Sahoo, KIIT
Disprove
Tractability
5
Tractable problems: Intractable problems:
Polynomial time Super Polynomial time
O(n2), O(n3), O(1),O(nlg n) O(2n), O(n 2n), O(nn),
O(n!)
O(n100) O(n 2n)
High order Polynomial (for n=10, small input)
Tractable Intractable
Biswajit Sahoo, KIIT
Disprove
Tractability
6
Tractable problems: Intractable problems:
Polynomial time algorithms Super Polynomial time
are Tractable Normally algorithms are
Intractable in General
Not applicable for: Not applicable for:
Higher order Polynomial Small inputs
Biswajit Sahoo, KIIT
Polynomial Time Nondeterministic Algorithm
7
int Search(a, n, key)
{ Running Time
i=choice(1 : n) //O(1) : Nondeterministic
if(key==a[i]) //1
return(i); //1
else
return(-1); //1
} Total Running time=O(1)
Assume time required for choice(1 : n) is O(1).
Biswajit Sahoo, KIIT
P and NP
8
P is set of problems that can be solved in polynomial
time in a deterministic machine
NP (nondeterministic polynomial time) is the set of
problems that can be solved in polynomial time by a
nondeterministic machine
A non-deterministic computer is a computer that
magically “guesses” a solution, then has to verify that it
is correct.
Is P = NP ?
Biswajit Sahoo, KIIT
P and NP
9
NP
Today nondeterministic, Tomorrow may be deterministic
Biswajit Sahoo, KIIT
Optimization and Decision Problems
10
Optimization Problem: Maximize profit or Minimize Loss
Decision Problem: Answers are in Boolean (Yes/No)
Optn: Find MCST of the graph, G.
Decn: Is there any MCST exist in G with cost less than k?
Optn: Find TSP (optimal) of the graph, G.
Decn: Is there any TSP exist in G with cost less than k?
Optn: Find maximum profit in a 0/1 Knapsack.
Decn: Does 0/1 Knapsack have a profit more than k?
Biswajit Sahoo, KIIT
Verification of Decision Problems
11
Ex:- TSP, Formula Satisfiability, 0/1 Knapsack...
Given a solution (guess) to the problem, we neeed to
verify it in the problem
NP problems are Verifiable in polynomial time in
deterministic machine
Biswajit Sahoo, KIIT
Verification of Decision TSP in P
12
3 4
5 8
6
Source 1
9
7
2
Biswajit Sahoo, KIIT
Verification of Decision TSP in P
13
3 4
5 8
1, 5, 3, 4, 8, 6, 9, 2, 7, 1 6
Source 1
9
7
2
Biswajit Sahoo, KIIT
Verification of Decision TSP in P
14
3 4
5 8
1, 5, 3, 4, 8, 6, 9, 2, 7, 1 6
Source 1
9
7
2
Biswajit Sahoo, KIIT
Verification of Decision TSP in P
15
3 4
5 8
1, 5, 3, 4, 8, 6, 9, 2, 7, 1 6
Source 1
9
7
2
Biswajit Sahoo, KIIT
Verification of Decision TSP in P
16
3 4
5 8
1, 5, 3, 4, 8, 6, 9, 2, 7, 1 6
Source 1
9
7
2
Biswajit Sahoo, KIIT
Verification of Decision TSP in P
17
3 4
5 8
1, 5, 3, 4, 8, 6, 9, 2, 7, 1 6
Source 1 Verified in P
9
7
2
Biswajit Sahoo, KIIT
Reducibility
18
The crux of NP-Completeness is Reducibility
Informally, a problem L can be reduced to another
problem Q if any instance of L can be “easily
rephrased” as an instance of Q, the solution to which
provides a solution to the instance of L
Intuitively: If L reduces to Q, L is “no harder to
solve” than Q
Biswajit Sahoo, KIIT
Reducibility Examples
19
Given an equation ax2 + bx + c = 0, find roots of the
equation.
Question: 5x + 6 = 0;
P
0.x2 + 5x + 6 = 0
Biswajit Sahoo, KIIT
Reducibility Examples
20
X: Given n integers, is the largest integer > 0 ?
Y: Given n Boolean variables, is there at least one
TRUE? X -1 -49 -4 5 1 0 -6 8 -20
Y F F F T T F F T F
Transform X to Y by yi = T if xi > 0, yi = F if xi <= 0
Time required Time required to Time required
= ＋
to test X reduce X to Y to test Y
Now, X is Polynomial-time Reducible to Y,
So, we denote this X p Y
Reducibility relation
21
Yes for A
Yes
α Poplynomial β Algorithm for
Reduction B N
o No for A
Decision Algorithm for A
A and B are two decision Problems
If decision algorithm for B is polynomial so does A
A is no harder than B
If A hard ( e.g. NPC) so does B
Biswajit Sahoo, KIIT
Transitive property of Reducibility
22
X, Y and Z are three problems;
X is Polynomial-time Reducible to Y, X p Y and
Y is Polynomial-time Reducible to Z, Y p Z
Now, X p Z; X is Polynomial-time Reducible to Z
Biswajit Sahoo, KIIT
P, NP, NP Complete and NP Hard
23
NP
NP Hard
P NPC
Today noddeterministic, Tomorrow may be deterministic
Biswajit Sahoo, KIIT
P & NP Defination
24
P = problems that can be solved in polynomial
time (quick solution)
NP = problems for which a solution can be
verified in polynomial time (quick verification)
Unknown whether P = NP ? (most suspect not)
Biswajit Sahoo, KIIT
NP Complete & NP Hard Defination
25
NP-Complete NP-Hard
Problem L is NP Complete, if Problem L is NP Hard if
L NP and
R p L R NP R p L R NP
Problem L is NP Complete, if Problem L is NP Hard if
L NP and
R p L for any R NPC R p L for any R NPC
Biswajit Sahoo, KIIT
NP-Complete Problems
26
Formula SAT
3Coloring 3-CNF SAT Clique Decision
Sum of Subset Hamiltonian Cycle
TSP
Biswajit Sahoo, KIIT
Maximum Clique Problem
27
1 2
4 3
Biswajit Sahoo, KIIT
Maximum Clique Problem
28
1 2 1 2
Clique of size 2
4 3 4 3
Biswajit Sahoo, KIIT
Maximum Clique Problem
29
1 2 2
4 3 4 3
Clique of size 3
4 3
5
Biswajit Sahoo, KIIT
Maximum Clique Problem
30
4 2
6 5
Biswajit Sahoo, KIIT
Maximum Clique Problem
31
4 2
3 Clique of size 2
6 5
Biswajit Sahoo, KIIT
Maximum Clique Problem
32
4 2
3 Clique of size 3
6 5
Biswajit Sahoo, KIIT
Maximum Clique Problem
33
4 2
3 Clique of size 4
6 5
Biswajit Sahoo, KIIT
Clique Decision Problem (CDP)
34
Is there a clique of size 3 in the graph?
Clique Decision Problem (CDC) is in NP-Complete?
i. CDC NP and
ii. 3-CNF SAT p CDC
if the formula is satisfiable then the graph has a
Clique of size 3.
Biswajit Sahoo, KIIT
Verification of CDP
35
CDC NP 1
4 2
6 5
Biswajit Sahoo, KIIT
Verification of CDP
36
CDC NP 1
4 2
3 Clique of size 3 (1, 2, 4)
Verified in polynomial time
6 5
Biswajit Sahoo, KIIT
Clique Decision Problem (CDP)
37
3-CNF SAT p CDP
p Gφ
The formula is satisfiable iff the graph Gφ has a
Clique of size 3.
Biswajit Sahoo, KIIT
X1
X3
X1
X2 X2
Biswajit Sahoo, KIIT
Assignment:
X1
X3
x1=0, x2=1, x3=1
TRUE
X1
X2 X2
Biswajit Sahoo, KIIT
Assignment:
x1=0, x2=1, x3=1
X1
X3 Satisfiable
Clique of size 3
X1
X2 X2
Biswajit Sahoo, KIIT
Assignment:
x1=0, x2=1, x3=1
X1
X3 Satisfiable
Clique of size 3
X1
X2 X2
Biswajit Sahoo, KIIT
Assignment:
x1=1, x2=0, x3=1
X1
X3 Not Satisfiable
Clique of size 3 ?
X1
X2 X2
Biswajit Sahoo, KIIT
Assignment:
x1=1, x2=0, x3=1
X1
X3 Not Satisfiable
No Clique of size 3
X1
X2 X2
Biswajit Sahoo, KIIT
Hamiltonian Cycle
44
Given a directed graph G = (V, E), we say that a
cycle C in G is a Hamiltonian cycle if it visits each
vertex exactly once. Find C in G.
Hamiltonian Cycle Problem: Given a G, does it
contain a Hamiltonian cycle?
Biswajit Sahoo, KIIT
Hamiltonian Cycle
45
Hamiltonian Cycle is in NP-Complete ?
■ Hamiltonian Cycle NP and
■ 3-CNF SAT p Hamiltonian Cycle
if the formula is satisfiable then the graph has a
Hamiltonian Cycle
Biswajit Sahoo, KIIT
Verification of Hamiltonian Cycle
46
Hamiltonian Cycle NP
3 4
5 8
1, 5, 3, 4, 8, 6, 9, 2, 7, 1 6
Source 1 Verified in P
9
7
2
Biswajit Sahoo, KIIT
Contd...
A
Widget
a a’
z1 z2 z3 z4
b b’
Biswajit Sahoo, KIIT
Contd...
a a’
z1 z2 z3 z4
b b’
a a’
z1 z2 z3 z4
b b’
Biswajit Sahoo, KIIT
Contd...
A
Widget
a a’
X
b b’
Biswajit Sahoo, KIIT
Contd...
b1
B
Widget
b2
b3
b4
Biswajit Sahoo, KIIT
Contd...
b1
B
Widget
b2
b3
b4
Biswajit Sahoo, KIIT
Contd...
b1
B
Widget
b2
b3
b4
Biswajit Sahoo, KIIT
Contd...
b1
B
Widget
b2
b3
b4
Biswajit Sahoo, KIIT
Contd...
b1
B
Widget
b2
b3
b4
Biswajit Sahoo, KIIT
Contd...
b1
B
Widget
b2
b3
b4
Biswajit Sahoo, KIIT
Contd...
B
Widget b1
b2
X
X
B All edges can not be traversed
opposite to widget B to visit
b3 remaining vetreces of the
Widget
b4
Biswajit Sahoo, KIIT
Contd...
B
Widget b1
b2
B A subset of the edges can be
traversed opposite to widget B
b3 to visit remaining vetreces of
the Widget B
b4
Biswajit Sahoo, KIIT
Reducing to Hamiltonian Cycle
58
3-CNF SAT p Hamiltonian Cycle
p GRAPH
if the formula is satisfiable then the Graph has a
Hamiltonian Cycle
Biswajit Sahoo, KIIT
b1 Contd...
1
x
b1 1
2
B1
e1
b1
3
b1
4
b2
1
x
2
b2
2
B2 e2
b2
3
b2
4
b3
1 x
3
b3
2
B3 e3
b3
3
b3
4
Biswajit Sahoo, KIIT
b1 Contd...
1
B1
b1
2 A 1
e1
b1
3
b1
4
b2
1
A
x
2
b2
2
B2 e2
b2
3 A
b2
4
b3
1 x
3
b3
2
B3 e3
b3
3
b3
4
Biswajit Sahoo, KIIT
b1 Contd...
1
B1
b1
2 A 1
e1
b1
3
b1
A
4
b2
1
A
x
2
b2
2 A
B2 e2
b2
3 A
b2
4
b3
1 x
A 3
b3
2
B3 e3
b3
3
b3
4
Biswajit Sahoo, KIIT
b1 Contd...
1
B1
b1
2 A 1
e1
b1
3
b1
A
4
b2
1
A
x
2
b2
2 A
B2 e2
b2
3 A A
b2
4
b3
1 x
A A 3
b3
2
B3 e3
b3
3
A
b3
4
Biswajit Sahoo, KIIT
b1 Contd...
1
B1
b1
2 A 1
e1
b1
3
x1 x2 x3
A
b1
4
0 1 1
b2
1
A
x
2
b2
2 A
B2 e2
b2
3 A A
b2
4
b3
1 x
A A 3
b3
2
B3 e3
b3
3
A
b3
4
Biswajit Sahoo, KIIT
b1 Contd...
1
B1
b1
2 A 1
e1
b1
3
x1 x2 x3
b1
A 0 1 1
4
Satisfiable
b2
1
A Hence, Cycle
x
2
b2
2 A
B2 e2
b2
3 A A
b2
4
b3
1 x
A A 3
b3
2
B3 e3
b3
3
A
b3
4
Biswajit Sahoo, KIIT
b1 Contd...
1
B1
b1
2 A 1
e1
b1
3 x1 x2 x3
b1
A 1 0 1
4
Not
b2
1
A Satisfiable
x
2
b2
2 A
B2 e2
b2
3 A A
b2
4
b3
1 x
A A 3
b3
2
B3 e3
b3
3
A
b3
4
Biswajit Sahoo, KIIT
b1 Contd...
1
B1
b1
2 A 1
e1
b1
3 x1 x2 x3
b1
A 1 0 1
4
Not
b2
1
A Satisfiable
x
2
b2
2 A
B2 e2
b2
3 A A
b2
4
b3
1 x
A A 3
b3
2
B3 e3
b3
3
A
b3
4
Biswajit Sahoo, KIIT
b1 Contd...
1
B1
b1
2 A 1
e1
b1
3 x1 x2 x3
b1
A 1 0 1
4
Not
b2
1
A Satisfiable
x
2 No Cycle
b2
2 A
B2 e2
b2
3 A A
b2
4
b3
1 x
A A 3
b3
2
B3 e3
b3
3
A
b3
4
Biswajit Sahoo, KIIT
Travelling Salesperson Problem (TSP)
68
Consider a salesman who must visit n cities labeled v1,
v2,..., vn.
The salesman starts in city v1, his home, and wants to
find a tour—an order in which to visit all the other
cities and return home. His goal is to find a tour that
causes him to travel as little total distance as possible.
Decision Travelling Salesman Problem: Given a set of
distances on n cities, and a bound D, is there a tour of
length at most D?
Biswajit Sahoo, KIIT
Travelling Salesperson Problem (TSP)
69
TSP is in NP-Complete ?
i. TSP NP
ii. Hamiltonian Cycle p TSP
if the graph (G) has a Hamiltonian Cycle then the
graph (G’) must have a TSP
TSP: Does the graph have a TSP whose cost is k?
Biswajit Sahoo, KIIT
Verification of decision TSP
70
TSP NP
3 4
5 8
1, 5, 3, 4, 8, 6, 9, 2, 7, 1 6
Source 1
Verified in P
9
7
2
Biswajit Sahoo, KIIT
Reducing to Travelling Salesperson Problem
71 (TSP)
Hamiltonian Cycle p TSP
G G’
Cost matrix of G is reduced to cost matrix of G’
cost(i, j) = 1 if an edge is there between i to j else 0
The reduction can be done in P i. e. O(n2),
considering n number of vertices
Biswajit Sahoo, KIIT
TSP of cost k?
72 Hamiltonian Cycle?
Hamiltonian Cycle pTSP
3 4
add cost 1
5 8
1, 5, 3, 4, 8, 6, 9, 2, 7, 1 6
Source 1
9
7
2
Biswajit Sahoo, KIIT
TSP of cost k?
73 Hamiltonian Cycle?
Hamiltonian Cycle pTSP
3 4
add cost 1
5 8
1, 5, 3, 4, 8, 6, 9, 2, 7, 1 6
Source 1
9
7
2
All edges are present, Hamiltonian cycle exists
Biswajit Sahoo, KIIT TSP exists with cost k
TSP of cost k?
74 Hamiltonian Cycle?
Hamiltonian Cycle pTSP
3 4
X No Edge(add cost 0)
add cost 1
5 8
1, 5, 3, 4, 8, 6, 9, 2, 7, 1 6
Source 1
9
7
2
No Hamiltonian cycle exists
Biswajit Sahoo, KIIT No TSP exist with cost k
75
Biswajit Sahoo, KIIT
