[Solved] Consider a graph G = (V, E) where I V I is divisible by 3. The problem of finding a Hamiltonian cycle in a graph is denoted by SHAM3 and the problem of determining if a Hamiltonian cycle exits in such graph is denoted by DHAM3. The option, which holds true, is

Q.	Consider a graph G = (V, E) where I V I is divisible by 3. The problem of finding a Hamiltonian cycle in a graph is denoted by SHAM3 and the problem of determining if a Hamiltonian cycle exits in such graph is denoted by DHAM3. The option, which holds true, is
A.	Only DHAM3 is NP-hard
B.	Only SHAM3 is NP-hard
C.	Both SHAM3 and DHAM3 are NP-hard
D.	Neither SHAM3 nor DHAM3 is NP-hard
Answer» C. Both SHAM3 and DHAM3 are NP-hard

Do you find this helpful?

View all MCQs in

Theory of Computation

Discussion

No comments yet

Related MCQs

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
Let FHAM be the problem of finding a Hamiltonian cycle in a graph G and DHAM be the problem of determining if a Hamiltonial cycle exists in a graph. Which one of the following is TRUE?
Which of the following statements are TRUE? (1) The problem of determining whether there exists a cycle in an undirected graph is in P. (2) The problem of determining whether there exists a cycle in an undirected graph is in NP. (3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
A Hamiltonian cycle in a Hamiltonian graph of order 24 has
Consider a string s over (0+1)*. The number of 0’s in s is denoted by no(s) and the number of 1’s in s is denoted by n1(s). The language that is not regular is
A minimum state deterministic finite automation accepting the language L={W W ε {0,1}*, number of 0s and 1s in are divisible by 3 and 5, respectively} has
A minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has
Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is
Consider three problems P1, P2 and P3. It is known that P1 has polynomial time solution and P2 is NP-complete and P3 is in NP. Which one of the following is true.
Consider the following CFG S → aB S → bA**spaceB → b A → a**spaceB → bS A → aS**spaceB → aBB A → bAA**space Consider the following derivation **spaceS ⇒aB**space⇒aaBB**space⇒aaBb**space⇒aabSb**space⇒aabbAb**space⇒aabbab**space This derivation is