Bharati Vidyapeeth (Deemed To Be University)
College of Engineering, Pune
DEPARTMENT OF COMPUTER ENGINEERING
DESIGN AND ANALYSIS OF ALGORITHMS
Practical No :- 10
NAME: Sashank Yadav
PRN NO.: 1814110120
ROLL NO.: 123
CLASS: B.TECH SEM V DIV-2
AIM :- Study NP Hard Graph , NP Hard Scheduling problem.
OBJECTIVE : To Learn whether all the computational problems be solved by
a computer.
THEORY
There are computational problems that can not be solved by algorithms even
with unlimited time. For example Turing Halting problem (Given a program and
an input, whether the program will eventually halt when run with that input, or
will run forever). Alan Turing proved that general algorithm to solve the halting
problem for all possible program-input pairs cannot exist. A key part of the proof
is, Turing machine was used as a mathematical definition of a computer and
program.
Status of NP Complete problems is another failure story, NP complete problems
are problems whose status is unknown. No polynomial time algorithm has yet
been discovered for any NP complete problem, nor has anybody yet been able
to prove that no polynomial-time algorithm exist for any of them. The interesting
part is, if any one of the NP complete problems can be solved in polynomial time,
then all of them can be solved.
What are NP, P, NP-complete and NP-Hard
Problems is set of problems that can be solved by a deterministic Turing
machine in Polynomial time.
NP is set of decision problems that can be solved by a Non-deterministic Turing
Machine in Polynomial time. P is subset of NP (any problem that can be solved
by deterministic machine in polynomial time can also be solved by non-
deterministic machine in polynomial time). Informally, NP is set of decision
problems which can be solved by a polynomial time via a “Lucky Algorithm”, a
magical algorithm that always makes a right guess among the given set of
choices
NP-complete problems are the hardest problems in NP set. A decision
problem L is NP- complete if:
1) L is in NP (Any given solution for NP-complete problems can be verified
quickly, but there is no efficient known solution).
2) Every problem in NP is reducible to L in polynomial time (Reduction is
defined below).
A problem is NP-Hard if it follows property 2 mentioned above, doesn’t need
to follow property
1. Therefore, NP-Complete set is also a subset of
NP-Hard set.
Decision vs Optimization
Problems
NP-completeness applies to the realm of decision problems. It was set up this
way because it’s easier to compare the difficulty of decision problems than that
of optimization problems. In reality, though, being able to solve a decision
problem in polynomial time will often permit us to solve the corresponding
optimization problem in polynomial time (using a polynomial number of calls to
the decision problem). So, discussing the difficulty of decision problems is often
really equivalent to discussing the difficulty of optimization problems.
(Source Ref 2). For example, consider the vertex cover problem (Given a
graph, find out the minimum sized vertex set that covers all edges). It is an
optimization problem. Corresponding decision problem is, given undirected
graph G and k, is there a vertex cover of size k?
What is Reduction?
Let L1 and L2 be two decision problems. Suppose algorithm A2 solves L2. That
is, if y is an input for L2 then algorithm A2 will answer Yes or No depending
upon whether y belongs to L2 or not. The idea is to find a transformation from
L1 to L2 so that the algorithm A2 can be part of an algorithm A1 to solve L1.
Learning reduction in general is very important. For example, if we have
library functions to solve certain problem and if we can reduce a new problem
to one of the solved problems, we save a lot of time. Consider the example of
a problem where we have to find minimum product path in a given directed
graph where product of path is multiplication of weights of edges along the
path. If we have code for Dijkstra’s algorithm to find shortest path, we can
take log of all weights and use Dijkstra’s algorithm to find the minimum
product path rather than writing a fresh code for this new problem
How to prove that a given problem is NP Complete?
From the definition of NP-complete, it appears impossible to prove that a
problem L is NP- Complete. By definition, it requires us to that show every
problem in NP is polynomial time reducible to L. Fortunately, there is an
alternate way to prove it. The idea is to take a known NP-Complete problem
and reduce it to L. If polynomial time reduction is possible, we can prove that L
is NP-Complete by transitivity of reduction (If a NP-Complete problem is
reducible to L in polynomial time, then all problems are reducible to L in
polynomial time).
What was the first problem proved as NP-Complete
There must be some first NP-Complete problem proved by definition of NP-
Complete problems. SAT (Boolean satisfiability problem) is the first NP-
Complete problem proved by Cook (See CLRS book for proof).
It is always useful to know about NP-Completeness even for engineers.
Suppose you are asked to write an efficient algorithm to solve an extremely
important problem for your company. After a lot of thinking, you can only come
up exponential time approach which is impractical. If you don’t know about NP-
Completeness, you can only say that I could not come with an efficient algorithm.
If you know about NP-Completeness and prove that the problem as NP-
complete, you can proudly say that the polynomial time solution is unlikely to
exist. If there is a polynomial time solution possible, then that solution solves a
big problem of computer science many scientists have been trying for years.
Cook's Theorem
Stephen Cook presented four theorems in his paper “The Complexity of Theorem
Proving Procedures”. These theorems are stated below. We do understand that
many unknown terms are being used in this chapter, but we don’t have any scope
to discuss everything in detail.
Following are the four theorems by Stephen Cook −
Theorem-1
If a set S of strings is accepted by some non-deterministic Turing machine within polynomial
time, then S is P-reducible to {DNF tautologies}.
Theorem-2
The following sets are P-reducible to each other in pairs (and hence each has the same
polynomial degree of difficulty): {tautologies}, {DNF tautologies}, D3, {sub-graph pairs}.
Theorem-3
• For any TQ(k) of type Q, TQ(k)k√(logk)2TQ(k)k(logk)2 is unbounded
• There is a TQ(k) of type Q such that TQ(k)⩽2k(logk)2TQ(k)⩽2k(logk)2
Theorem-4
If the set S of strings is accepted by a non-deterministic machine within time T(n) = 2n, and
if TQ(k) is an honest (i.e. real-time countable) function of type Q, then there is a constant K,
so S can be recognized by a deterministic machine within time TQ(K8n).
• First, he emphasized the significance of polynomial time reducibility. It means that if we
have a polynomial time reduction from one problem to another, this ensures that any
polynomial time algorithm from the second problem can be converted into a
corresponding polynomial time algorithm for the first problem.
• Second, he focused attention on the class NP of decision problems that can be solved
in polynomial time by a non-deterministic computer. Most of the intractable problems
belong to this class, NP.
• Third, he proved that one particular problem in NP has the property that every other
problem in NP can be polynomially reduced to it. If the satisfiability problem can be
solved with a polynomial time algorithm, then every problem in NP can also be solved
in polynomial time. If any problem in NP is intractable, then satisfiability problem must
be intractable. Thus, satisfiability problem is the hardest problem in NP.
• Fourth, Cook suggested that other problems in NP might share with the satisfiability
problem this property of being the hardest member of NP.
Kosaraju’s Algorithm:-
The Kosaraju algorithm is a DFS based algorithm used to find Strongly
Connected Components(SCC) in a graph. It is based on the idea that if
one is able to reach a vertex v starting from vertex u, then one should be
able to reach vertex u starting from vertex v and if such is the case, one
can say that vertices u and v are strongly connected - they are in a
strongly connected sub-graph.
Algorithm:-
The algorithm consists of three steps:
1. Do a DFS on the original graph: Do a DFS on the original graph,
keeping track of the finish times of each node. This can be done
using a stack, when a DFS finishes put the source vertex on the
stack. This way node with highest finishing time will be on top of
the stack.
2. Reverse the original graph: Reverse the graph using an adjaceny
list.
3. Do DFS again: Do DFS on the reversed graph, with the source
vertex as the vertex on top of the stack. When DFS finishes, all
nodes visited will form one Strongly Connected Component. If any
more nodes remain unvisited, this means there are more Strongly
Connected Component's, so pop vertices from top of the stack until
a valid unvisited node is found. This will have the highest finishing
time of all currently unvisited nodes. This step is repeated until all
nodes are visited.
Pseudo code for Kosaraju’s algorithm:-
stack STACK
void DFS(int source) {
visited[s]=true
for all neighbours X of source that are not visited:
DFS(X)
STACK.push(source)
}
CLEAR ADJACENCY_LIST
for all edges e:
first = one end point of e
second = other end point of e
ADJACENCY_LIST[second].push(first)
while STACK is not empty:
source = STACK.top()
STACK.pop()
if source is visited :
continue
else :
DFS(source)
Satisfiable Problem
Code
// C++ implementation to find if the given
// expression is satisfiable using the
// Kosaraju's Algorithm
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100000;
// data structures used to implement Kosaraju's
// Algorithm. Please refer
// http://www.geeksforgeeks.org/strongly-connected-components/
vector<int> adj[MAX];
vector<int> adjInv[MAX];
bool visited[MAX];
bool visitedInv[MAX];
stack<int> s;
// this array will store the SCC that the
// particular node belongs to
int scc[MAX];
// counter maintains the number of the SCC
int counter = 1;
// adds edges to form the original graph
void addEdges(int a, int b)
adj[a].push_back(b);
// add edges to form the inverse graph
void addEdgesInverse(int a, int b)
adjInv[b].push_back(a);
// for STEP 1 of Kosaraju's Algorithm
void dfsFirst(int u)
if(visited[u])
return;
visited[u] = 1;
for (int i=0;i<adj[u].size();i++)
dfsFirst(adj[u][i]);
s.push(u);
// for STEP 2 of Kosaraju's Algorithm
void dfsSecond(int u)
if(visitedInv[u])
return;
visitedInv[u] = 1;
for (int i=0;i<adjInv[u].size();i++)
dfsSecond(adjInv[u][i]);
scc[u] = counter;
}
// function to check 2-Satisfiability
void is2Satisfiable(int n, int m, int a[], int b[])
// adding edges to the graph
for(int i=0;i<m;i++)
// variable x is mapped to x
// variable -x is mapped to n+x = n-(-x)
// for a[i] or b[i], addEdges -a[i] -> b[i]
// AND -b[i] -> a[i]
if (a[i]>0 && b[i]>0)
addEdges(a[i]+n, b[i]);
addEdgesInverse(a[i]+n, b[i]);
addEdges(b[i]+n, a[i]);
addEdgesInverse(b[i]+n, a[i]);
else if (a[i]>0 && b[i]<0)
addEdges(a[i]+n, n-b[i]);
addEdgesInverse(a[i]+n, n-b[i]);
addEdges(-b[i], a[i]);
addEdgesInverse(-b[i], a[i]);
}
else if (a[i]<0 && b[i]>0)
addEdges(-a[i], b[i]);
addEdgesInverse(-a[i], b[i]);
addEdges(b[i]+n, n-a[i]);
addEdgesInverse(b[i]+n, n-a[i]);
else
addEdges(-a[i], n-b[i]);
addEdgesInverse(-a[i], n-b[i]);
addEdges(-b[i], n-a[i]);
addEdgesInverse(-b[i], n-a[i]);
// STEP 1 of Kosaraju's Algorithm which
// traverses the original graph
for (int i=1;i<=2*n;i++)
if (!visited[i])
dfsFirst(i);
// STEP 2 pf Kosaraju's Algorithm which
// traverses the inverse graph. After this,
// array scc[] stores the corresponding value
while (!s.empty())
{
int n = s.top();
s.pop();
if (!visitedInv[n])
dfsSecond(n);
counter++;
for (int i=1;i<=n;i++)
// for any 2 vairable x and -x lie in
// same SCC
if(scc[i]==scc[i+n])
cout << "The given expression "
"is unsatisfiable." << endl;
return;
// no such variables x and -x exist which lie
// in same SCC
cout << "The given expression is satisfiable."
<< endl;
return;
// Driver function to test above functions
int main()
// n is the number of variables
// 2n is the total number of nodes
// m is the number of clauses
int n = 5, m = 7;
// each clause is of the form a or b
// for m clauses, we have a[m], b[m]
// representing a[i] or b[i]
// Note:
// 1 <= x <= N for an uncomplemented variable x
// -N <= x <= -1 for a complemented variable x
// -x is the complement of a variable x
// The CNF being handled is:
// '+' implies 'OR' and '*' implies 'AND'
// (x1+x2)(x2'+x3)(x1'+x2')(x3+x4)(x3'+x5)*
// (x4'+x5')*(x3'+x4)
int a[] = {1, -2, -1, 3, -3, -4, -3};
int b[] = {2, 3, -2, 4, 5, -5, 4};
// We have considered the same example for which
// Implication Graph was made
is2Satisfiable(n, m, a, b);
return 0;
Output
APPROXIMATION PROBLEM:-
Approximation algorithm:-
An Approximate Algorithm is a way of approach NP-COMPLETENESS for
the optimization problem. This technique does not guarantee the best
solution. The goal of an approximation algorithm is to come as close as
possible to the optimum value in a reasonable amount of time which is at
the most polynomial time. Such algorithms are called approximation
algorithm or heuristic algorithm.
For the traveling salesperson problem, the optimization problem is to
find the shortest cycle, and the approximation problem is to find a short
cycle.
For the vertex cover problem, the optimization problem is to find the
vertex cover with fewest vertices, and the approximation problem is to
find the vertex cover with few vertices.
Travelling Salesman Problem:-
In the traveling salesman Problem, a salesman must visits n cities. We
can say that salesman wishes to make a tour or Hamiltonian cycle,
visiting each city exactly once and finishing at the city he starts from.
There is a non-negative cost c (i, j) to travel from the city i to city j. The
goal is to find a tour of minimum cost. We assume that every two cities
are connected. Such problems are called Traveling-salesman problem
(TSP).
We can model the cities as a complete graph of n vertices, where each
vertex represents a city.
It can be shown that TSP is NPC.
If we assume the cost function c satisfies the triangle inequality, then we
can use the following approximate algorithm.
Naive Solution:
1) Consider city 1 as the starting and ending point.
2) Generate all (n-1)! Permutations of cities.
3) Calculate cost of every permutation and keep track of minimum cost
permutation.
4) Return the permutation with minimum cost.
Time Complexity: Θ(n!)
CODE (Naïve approach):-
// CPP program to implement traveling salesman
// problem using naive approach.
#include <bits/stdc++.h>
using namespace std;
#define V 4
// implementation of traveling Salesman Problem
int travllingSalesmanProblem(int graph[][V], int s)
// store all vertex apart from source vertex
vector<int> vertex;
for (int i = 0; i < V; i++)
if (i != s)
vertex.push_back(i);
// store minimum weight Hamiltonian Cycle.
int min_path = INT_MAX;
do {
// store current Path weight(cost)
int current_pathweight = 0;
// compute current path weight
int k = s;
for (int i = 0; i < vertex.size(); i++) {
current_pathweight += graph[k][vertex[i]];
k = vertex[i];
current_pathweight += graph[k][s];
// update minimum
min_path = min(min_path, current_pathweight);
} while (
next_permutation(vertex.begin(), vertex.end()));
return min_path;
}
// Driver Code
int main()
// matrix representation of graph
int graph[][V] = { { 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 } };
int s = 0;
cout << travllingSalesmanProblem(graph, s) << endl;
return 0;
Output
Conclusion
In this practical, we studied about NP Hard graphs, Cook’s theorem,
Kosaraju’s algorithm, and approximation algorithm and also
implemented the code for them.
