The GATE Grind

GATE 2014 CS (CS3) – Question 48

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

2CNFSAT consists of satisfiable propositional CNF formulas with at most two literals per clause; for example $(x_1\lor x_2)\land(x_1\lor\overline{x_3})\land(x_2\lor x_4)$. The decision problem is ______.

  1. NP-complete
  2. solvable in polynomial time by reduction to directed graph reachability
  3. solvable in constant time because every instance is satisfiable
  4. NP-hard but not NP-complete

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) solvable in polynomial time by reduction to directed graph reachability

Explanation

For each clause(a∨b), add implication edges¬a→band¬b→a. A formula is satisfiable exactly when no variable and its negation lie in the same strongly connected component. Reachability/SCCanalysis is polynomial, giving **B**. Some2CNFformulas are unsatisfiable, so constant acceptance is invalid.