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?