Complexity of this variant of the Monotone(+,2−) -SAT problem?

Question

In this post,Monotone$(+, 2^-)$-SAT problem is defined as follows:

Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF formula $F_2^-$ defined on the same variables as $F^+$, where all variables are negated. Is $F^+ \land F_2^-$ satisfiable ?), let us define the Monotone$(+, 2^-)$-SAT problem:

Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF formula $F_2^-$ defined on the same variables as $F^+$, where all variables are negated. Is $F^+ \land F_2^-$ satisfiable ?

Consider this variant of Monotone(+,2−)-SAT problem where we restrict the number of clause of $F^+$ to be 2 and the width of these 2 clause can be anything ,that means that every instance of positive literal appears in only 2 clause.

Is this variant also NP-complete? I don't see any direct reduction from the main problem to this variant ,so does there exist any reduction or is it solvable in polynomial time?

Answer 1

It is in P. Suppose the first clause of $F^+$ has $k_1$ variables, and the second clause has $k_2$ variables. Then there are $k_1 k_2$ ways to pick one variable from the first clause, and one variable from the second clause. For each such way, set those variables to true in $F_2^-$ (i.e., replace those variables with true, and simplify). The result is a 2-CNF formula, and you can test satisfiability of it in linear time. Check whether the result is satisfiable. If it is, then you obtain a satisfying assignment for $F^+ \land F_2^-$. Repeat once for each of these $k_1 k_2$ possibilities.