NP-Complete Problems. Hamiltonian-Cycle problem is the problem that takes a grap
ID: 664440 • Letter: N
Question
NP-Complete Problems.
Hamiltonian-Cycle problem is the problem that takes a graph as input and asks whether there is a simple cycle in G that visits each vertex of G exactly once and then return to its starting vertex. Such a cycle is called a Hamiltonian cycle of G. Describe a nondeterministic polynomial time algorithm for this problem.
The 3-Partition problem is defined as follows. Given a finite set A of 3m elements, a bound B Z+ (a positive integer) and a size s(a) Z+ for each element a A such that s(a) satisfies the following inequalities: B/4 < s(a) < B/2 and such that .
Can A be partitioned into m disjoint sets S1, S2, …, Sm such that, for 1 i m,
?
Describe a nondeterministic polynomial time algorithm for this problem.
How would you go about proving that the above two problems are indeed NP-Complete?
If Professor Weise arrives at describing a deterministic polynomial algorithm for any of the above problems, what conclusions would you draw? Justify your answer.
Explanation / Answer
Consider two decision problems X, Y and X belongs to NP-complete.
Then, to prove Y is NP-complete we have to show:
(1) Y belongs to NP, and
(2) X is a polynomial-time reducible to Y (transforming instance of X to instance of Y).
To prove Hamilton-cycle is NP-complete, first it is prove that the Hamilton-cycle is NP and then a NP-complete problem is reducible to Hamilton-cycle problem.
Proving Hamilton cycle problem is in NP:
Let the algorithm H is a deterministic algorithm. Algorithm H takes a graph of ‘n’ vertices. Each vertex in G is numbered from 1 to n.
Let the algorithm finds a sequence(S) of nodes in the graph.
To prove a problem is in NP, it is enough to prove that the problem can be verifiable (i.e. verifying whether the output produced by the algorithm is correct or not) in polynomial time.
Now, it is enough to verify that whether the sequence (S) contains all nodes or not and whether the sequence contains loops or not.
As the sequence S is of size n, the above two checks can be accomplish in polynomial time of n.
Therefore, the verification that whether the output contains Hamilton cycle or not, can be performed in polynomial time.
Hence, the Hamilton cycle problem is in NP. --- (1)
Further to prove this problem is in NP-complete, a NP problem is required. Choose, vertex cover problem that is NP-complete.
Vertex-cover problem: vertex cover algorithm takes a graph G and finds a sub set of vertices in graph G such that, for every edge (v,w) of G, v belongs to C or w belongs to C.
Now, it is enough to reduce vertex cover problem to Hamiltonian cycle problem.
To do this, take instance (G,k) of the Vertex cover problem. now construct a graph H that has a Hamiltonian cycle iff G has a vertex cover of size k.
Let the G has vertex cover of size k. the set is ={x1, x2, x3,….xk }. Construct a graph H using these vertices. We can prove that the graph H has a Hamiltonian cycle.
Conversely we can prove that if H has hamiltanion cycle , then G has vertex cover of size k.
Therefore, G has a vertex cover of size k iff H has Hamiltonian cycle. That is vertex problem can be reduced to Hamiltonian cycle problem. ---- (2)
Hence, from (1) and (2) , the Hamiltonian cycle problem is NP-Complete.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.