GATE CSE Graph Algorithms & P/NP Completeness – Algorithms Practice Test

GATE CSE Graph Algorithms & P/NP Completeness – Algorithms Practice Test | Set 1

Questions 86-90 of 100

0% completed (0/100 answered)

Question 86

MSQ · Multiple Correct 2 mark

Which statements about Clique and Independent Set are CORRECT?

A A clique in G is an independent set in the complement graph. B $\alpha(G) = \omega(complement(G)).$ C Every maximal clique has maximum possible size. D Maximum Clique is NP-hard.

Question 87

MSQ · Multiple Correct 2 mark

Which statements about approximation and NP-hardness are CORRECT?

A A polynomial-time approximation algorithm with ratio 1 is exact. B An exact polynomial-time algorithm for an NP-complete problem implies $P=NP$. C NP-hardness alone does not imply that a problem has no polynomial-time approximation algorithm. D Every NP-hard problem has a polynomial-time approximation scheme.

Question 88

MSQ · Multiple Correct 2 mark

Which statements about Eulerian and Hamiltonian problems are CORRECT?

A Hamiltonian cycle concerns visiting every vertex exactly once and returning to the start. B Hamiltonian cycle is known to be in P. C Eulerian circuit existence in an undirected graph is testable in polynomial time. D Eulerian circuit concerns using every edge exactly once.

Question 89

NAT · Numerical Answer 2 mark

A simple directed graph has 8 vertices. What is the maximum possible number of directed edges if self-loops are not allowed?

Enter your numerical answer

Question 90

NAT · Numerical Answer 2 mark

A simple undirected graph has 10 vertices and is complete. How many edges does it contain?

Enter your numerical answer