12
$\begingroup$

I am trying to solve this problem and I am really struggling.

A monotone boolean formula is a formula in propositional logic where all the literals are positive. For example,

$\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor x_4 \lor x_5)$

is a monotone boolean function. On the other hand, something like

$\qquad (x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor x_3) \land (\neg x_1 \lor x_5)$

is not a monotone boolean function.

How can I prove NP-completeness for this problem:

Determine whether a monotone boolean function is satisfiable if $k$ variables or fewer are set to $1$?

Clearly, all the variables could just be set to be positive, and that's trivial, so that is why there is the restraint of $k$ positively set variables.

I have tried a reduction from SAT to monotone boolean formula. One thing I have tried is to substitute a dummy variable in for every negative literal. For example, I tried replacing $\neg x_1$ with $z_1$, and then I tried forcing $x_1$ and $z_1$ to be different values. I haven't quite been able to get this to work though.

$\endgroup$
  • $\begingroup$ Welcome! Please take more care with language and formatting. $\endgroup$ – Raphael Apr 26 '13 at 9:59
12
$\begingroup$

The "parent" of the problem you're looking at is sometimes called Weighted Satisfiability (WSAT, particularly in parameterized complexity) or Min-Ones (though this is normally an optimization version, but near enough). These problems have the "at most $k$ variables set to true" restriction as their defining feature.

The restriction to monotone formulae is actually surprisingly easy to show hardness for, you just need to thing outside satisfiability problems for a moment. Instead of trying to modify a SAT instance, we instead start with Dominating Set (DS).

See if you can get it from there. More is in the spoilers, broken into bits, but avoid them if you can. I won't show membership in NP, you should have no problem with that.

Given an instance $(G, k)$ of DS (i.e. we want a dominating set of size at most $k$ for $G$), we can construct an instance $(\phi,k)$ of WSAT where the formula $\phi$ is a monotone CNF formula:

The basic construction:

For each $v\in V(G)$ we have a variable $v' \in \text{var}(\phi)$, for each $v \in V(G)$ we have a clause $c_{v} = \bigvee_{u\in N(v)} u'$.

A sketch of the proof:

Each vertex either has to be in the dominating set, or have a neighbour that is, so if we can find $k$ vertices that form a dominating set, the corresponding $k$ variables can be set to true in $\phi$, and each clause must contain at least one of them. Similarly if there is a weight $k$ satisfying assignment, the true variables correspond to the vertices we place in the dominating set - every clause $c_{v}$ must have at least one, so each $v$ is dominated (by itself or otherwise).

$\endgroup$
  • $\begingroup$ Wow this makes so much more sense, thank you! I think I was definitely caught up in trying to reduce SAT down to the monotone boolean formula. $\endgroup$ – nat Apr 26 '13 at 0:56
  • $\begingroup$ I'm also seeing that we can also reduce the vertex cover down to the monotone boolean formula. $\endgroup$ – nat Apr 26 '13 at 1:21
  • 1
    $\begingroup$ @nat indeed, the going from vertex cover is also nice because it gives you a formula in 2CNF, which is interesting as 2-SAT is in P, but monotone WSAT with 2CNF formulae is NP-complete. Coincidentally, you can also get antimonotone results (where every variable is negated, but you want at least $k$ true variables) from Clique/Independent set. If you're particularly keen, you may want to look into Parameterized Complexity, where these sort of satisfiability problems play central roles. $\endgroup$ – Luke Mathieson Apr 26 '13 at 1:48
  • $\begingroup$ I think that exactly the same approach works with verticles coverage. $\endgroup$ – Haskell Fun Aug 28 '17 at 10:17
  • $\begingroup$ @HaskellFun, I thought about this also. Vertex cover is the same as monotone Min-W2SAT. $\endgroup$ – rus9384 Aug 28 '17 at 11:33
2
$\begingroup$

There is a simple reduction from SAT. Introduce a new variable $z_i$ to represent $\neg x_i$. Given a formula $\phi$, we create a new formula $\phi'$ by replacing each occurrence of $\neg x_i$ with $z_i$, and adding the clause $x_i \vee z_i$ for each variable. We set $k$ to be the number of original variables. The new formula $\phi'$ is monotone, and is satisfiable with at most k variables set to true if and only if $\phi$ is satisfiable. (This is because the $k$ disjoint clauses $x_i \vee z_i$ causes any satisfying assigment for $\phi'$ to have at least $k$ variables to True; but then the only way to have at most $k$ is to have exactly one of them set to true for each pair {x_i, z_i}.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.