Consider the decision problem $2CNFSAT$ defined as follows: $\Phi \mid \Phi$ is a satisfiable propositional formula in CNF with at most two literals per clause For example, $\Phi = (x_1 \vee x_2) \wedge (x_1 \vee \overline{x_3}) \wedge (x_2 \vee x_4)$ is a Boolean formula and it is in $2CNFSAT$. The decision problem $2CNFSAT$ is (A) NP-Complete. (B) solvable in polynomial time by reduction to directed graph reachability. (C) solvable in constant time since any input instance is satisfiable. (D) NP-hard, but not NP-complete.

The 2-Satisfiability (2-SAT or 2CNFSAT) problem can be solved in linear (and therefore polynomial) time by constructing an implication graph:

1. Each clause of the form $(a \vee b)$ is equivalent to two implications: $(

eg a \to b)$and$( eg b \to a)$.

2. In the directed implication graph, each variable $x_i$ and its negation $

eg x_i$ are represented as vertices, and each implication represents a directed edge.

3. The formula is satisfiable if and only if no variable $x_i$ and its negation $

eg x_i$belong to the same Strongly Connected Component (SCC), which is equivalent to checking directed reachability between$x_i$and$ eg x_i$.

Since computing strongly connected components or testing reachability takes $O(V + E)$ time using algorithms like Kosaraju's or Tarjan's, the problem is solvable in polynomial time by reduction to directed graph reachability.

Therefore, option (B) is correct.