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

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

Questions 81-85 of 100

0% completed (0/100 answered)

Question 81

MSQ · Multiple Correct 2 mark

Which statements about flow networks are CORRECT?

A Any augmenting path proves the current flow is maximum. B A saturated forward edge has zero residual capacity in that direction. C A feasible flow must satisfy flow conservation at every vertex except s and t. D Residual edges can have capacity representing the ability to cancel existing flow.

Question 82

MSQ · Multiple Correct 2 mark

Which statements about P, NP, and NP-completeness are CORRECT?

A If a problem is NP-hard, it must be in NP. B If any NP-complete problem is in P, then $P = NP$. C Every NP-complete problem is NP-hard. D P is a subset of NP.

Question 83

MSQ · Multiple Correct 2 mark

Which of the following are NP-complete decision problems?

A 3-SAT B Clique C Minimum Spanning Tree D Vertex Cover

Question 84

MSQ · Multiple Correct 2 mark

Which statements about reductions are CORRECT?

A If A <=_p B and A is NP-hard, then B is NP-hard. B If A <=_p B and B is in P, then A is in P. C Polynomial-time reductions are transitive. D If A <=_p B and B is NP-hard, then A is NP-hard.

Question 85

MSQ · Multiple Correct 2 mark

Which statements about 2-SAT are CORRECT?

A A formula is satisfiable iff no variable and its negation occur in the same SCC. B 2-SAT is NP-complete. C Its implication graph has two literals per variable. D 2-SAT can be solved in polynomial time.