2-SAT Problem with additional constraints on variable? Given a 2-SAT problem that is satisfiable. The solution to the problem can be found in polynomial time.

Adding an additional constraint:


The maximum number of positive literals that can have the boolean Value 1 is N. (i.e. a=positive literal, ~a=negative literal)


Is the problem still solvable in Polynomial time?

My assumption is it should be but I am unclear now to modify the original solution? Or are we looking at something similar to the Vertex Cover Problem?
That is NP-hard by reduction from vertex cover, even when there are no negative literals.

If you meant to count by occurrences rather than just bounding the number of

distinct variables which are true, then use this paper's result and this paper's result.