(a) Hamiltonian-Cycle problem is the problem that takes a graph as input and asks whether there...

 

Transcribed Image Text:

(a) Hamiltonian-Cycle problem is the problem that takes a graph as input and asks whether there is a simple cycle in 6 that visits each vertex of 6 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. (b) 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 Σs(a) = mB. Qe A Can A be partitioned into m disjoint sets S1, S2, ..., Sm such that, for 1 ≤ i ≤m, Σs(a) =B? de S Describe a nondeterministic polynomial time algorithm for this problem. (c) How would you go about proving that the above two problems are indeed NP- Complete? (d) If Professor Weise arrives at describing a deterministic polynomial algorithm for any of the above problems, what conclusions would you draw? Justify your answer. (a) Hamiltonian-Cycle problem is the problem that takes a graph as input and asks whether there is a simple cycle in 6 that visits each vertex of 6 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. (b) 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 Σs(a) = mB. Qe A Can A be partitioned into m disjoint sets S1, S2, ..., Sm such that, for 1 ≤ i ≤m, Σs(a) =B? de S Describe a nondeterministic polynomial time algorithm for this problem. (c) How would you go about proving that the above two problems are indeed NP- Complete? (d) If Professor Weise arrives at describing a deterministic polynomial algorithm for any of the above problems, what conclusions would you draw? Justify your answer.

Answer rating: 100% (QA)

a A nondeterministic polynomialtime algorithm for the HamiltonianCycle problem can be described as follows 1 Nondeterministically choose a permutation ... View the full answer