Scribd
Upload
78 views11 pages

Proof of NP Complete Problems-1

The document discusses NP-Complete problems, specifically the Traveling Salesperson Problem (TSP) and the 0/1 Knapsack Problem. It explains the relationship between TSP and the Hamiltonian Path Problem, providing a proof that TSP is NP Complete. Additionally, it compares the 0/1 Knapsack Problem to the Satisfiability (SAT) Problem, concluding that both are NP Complete.

Uploaded by

sindhuvaishnavi5
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
78 views11 pages

Proof of NP Complete Problems-1

The document discusses NP-Complete problems, specifically the Traveling Salesperson Problem (TSP) and the 0/1 Knapsack Problem. It explains the relationship between TSP and the Hamiltonian Path Problem, providing a proof that TSP is NP Complete. Additionally, it compares the 0/1 Knapsack Problem to the Satisfiability (SAT) Problem, concluding that both are NP Complete.

Uploaded by

sindhuvaishnavi5
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

NP-Complete Problems

Dr. [Link]
Asst. Prof., Dept of CSE
TRAVELLING SALES PERSON
PROBLEM (TSP)

 Let G = (V', E) be a directed graph


defining an instance of the traveling
salesperson problem. Let Cij equal the
cost of edge (i, j), Cij = ∞ if (i, j) != E, and
let IVI = n, without loss of generality, we
can assume that every tour starts and
ends at vertex 1.
Proof:TSP is NP Complete
Known NP Complete Problem:
Hamiltonian Path

To prove TSP is NP Hard

Hamiltonian path α TSP


Hamiltonian Cycle Problem
 Hamiltonian Cycle is a cycle in a directed or
undirected graph that visits each vertex exactly
once . Given a graph, start from an initial vertex,
visit all vertices exactly once and come back to
the initial [Link] forms a cycle.

 Similar to TSP. TSP is a minimization problem. It


focuses on optimal tour.

 In Hamiltonian cycle problem we have to find all


possible tours.
Hamiltonian Cycle Problem(Contd..)

Hamiltonian Cycle exist

Hamiltonian Cycle
doesn’t exist
Proof:TSP is NP Complete
Step 1: Consider an instance of Hamiltonian path
problem..rep as G
Step 2:
a) Construct a complete graph for G
b) Construct the complement for the graph G
c) Define the cost function for the complete
graph
c(i,j)=0….if(i,j) Є E
c(i,j)=1…if(i,j) does not belong to E
Step 3: Conclude Graph G has a Hamiltonian cycle
iff G’ has a tour of minimum cost (0)
Proof:TSP is NP Complete
Proof:TSP is NP Complete
O/1 Knapsack is NP Complete
0/1 Knapsack Problem
P={ 10, 8, 12} n=3
W={ 5,4,3} m=8
x1=0/1, x2=0/1, x3=0/1 23 => 2n

 Solution is similar to Satisfiability (SAT) Problem


 In SAT Problem we try to check if the formula is
true or not
 In 0/1 Knapsack problem we try to check if the
profit is maximized or not
 The problem can also be solved using state space
tree
SAT and 0/1 Knapsack Problem

 State space tree drawn represents both SAT


and 0/1 Knapsack problem
 If the SAT Problem can be solved in
Polynomial time related problems also can
be solved in polynomial time
 Therefore 0/1 Knapsack is NP complete.

You might also like