2
$\begingroup$

I am to prove that monotone boolean formula satisfiability checking when at most k variables are set to 1 is an NP-Complete problem. Proving that it is in NP is easy, but I'm having difficulty showing that it is in NP-Hard. I have seen this, but I would rather not use its solution, as the textbook for the course I am self studying does not present Dominating Sets as an NP-Complete problem. The NP-Complete problems presented in my book(Dasgupta, Papadimitriou, and Vazirani) are the following: 3SAT, Traveling Salesman, Longest Path, 3D-Matching, Knapsack, Independent Set (related to Dominating Set from what I understand), Vertex Cover, Clique, Integer Linear Programming, Rudrata Path, and Balanced Cut.

From my understanding of the problem, if you restrict the clauses to 2 literals each, then this directly parallels the vertex cover problem, and is thus NP-hard. I was wondering if there was any way that I could use this fact to say that the unrestricted problem is also NP-Hard. I intuitively feel that this should work, because the restricted version is a subset of the restricted version, so in at least some cases the problem is NP-hard. Since you always take the worst case scenario, could you extend this to NP-hardness for the unrestricted problem? If so, how would I word that (this is for a self study, not to be turned in), in the proper form? Because my above explanation has a roundabout method of showing the point.

tl;dr Can you prove that something is np-hard by showing that a subproblem is np-hard? I intuitively feel like you should, but want to confirm.

$\endgroup$
3
$\begingroup$

Let $L'$ be a restriction of $L$, say $L' = L \cap D$. Here $D$ is a restriction on the inputs such as "all clauses have two literals each".

Suppose that $L'$ is NP-hard. Then for every language $M$ in NP, there is a polytime reduction $\varphi$ from $M$ to $L'$ such that $x \in M$ iff $\varphi(x) \in L'$. If $\varphi(x) \in D$ for all $x$, then $\varphi(x) \in L'$ iff $\varphi(x) \in L$, and so $\varphi$ is also a reduction from $M$ to $L$.

Usually NP-hardness proofs go by reduction from some specific NP-complete problem $M$. If the polytime reduction $\varphi$ from $M$ to $L'$ showing that $L'$ is NP-hard satisfies the property $\varphi(x) \in D$ for all $x$ (in other words, its range is [contained in] $D$), then the reasoning in the preceding paragraph shows that $\varphi$ also proves that $L$ itself is NP-hard.

For example, in your case $L$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone Boolean formula that can be satisfies by setting at most $k$ of the literals to TRUE; $D$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone 2CNF; and $L' = L \cap D$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone 2CNF that can be satisfied by setting at most $k$ of the literals to TRUE. Any reduction $\varphi$ showing that $L'$ is NP-complete whose range is $D$ also shows that $L$ is NP-complete.

To check that you understand the argument, try to see what goes wrong when we take $L'$ to be, say, 3SAT, and $L$ to be the language of all 3CNFs.

Finally, here is a trick that you can use to emulate SAT in your setting. Suppose that some CNF $\varphi$ has variables $x_1,\ldots,x_n$, some of them possibly appearing negated. Consider $\psi = \varphi' \land (x_1 \lor y_1) \land \cdots \land (x_n \lor y_n)$, where $\varphi'$ results from replacing $\lnot x_i$ by $y_i$. Then $\varphi$ is satisfiable iff $\psi$ is satisfiable by a truth assignment in which at most (or exactly) $n$ variables are TRUE.

$\endgroup$
  • $\begingroup$ I'm marking your answer as correct, but I have one more question. On the part where you were emulating SAT by replacing the negated variables. I don't see how that replacement could work, because it allows both $x_i$ and $y_i$ to be true, which is equivalent to $x_i$ and $\lnot x_i$ both being true which is a logical impossibility? $\endgroup$ – Nezo Jul 8 '14 at 18:27
  • $\begingroup$ @SamadwaraReddy I suggest you reflect more on the issue. $\endgroup$ – Yuval Filmus Jul 8 '14 at 19:34

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.