# Reduce CNF-SAT to decision problem

Given CNF-SAT reduce it to the following decision problem:

Given n items, m groups (and for each group a set of items) and a parameter k. The problem outputs yes/no if there exists k or less groups such that every item is at least in one of the selected groups.

How can I reduce the CNF-SAT to this problem?

I get stuck when it comes to negative literals in the CNF-SAT. Because otherwise I could reduce it in the following way:

Each clause is a group and literals in the group are the items. parameter k is the number of clauses. If we find k or less groups that contain all literals, then they must be also contained in other clauses so we successfully reduced the CNF-SAT.

How can I incorporate negative literals in the reduction?

• What have you tried? We will be glad to help, but you have to show some effort, instead of us solving it for you. Commented Jan 7 at 15:06
• I've edited the question. Commented Jan 7 at 15:19
• Note: this problem is called set cover Commented Jan 7 at 22:50
• Good to know, is there any known SAT to Set cover reduction? @Nathaniel Commented Jan 7 at 23:07

It is not clear in your solution why treating clauses as groups helps. Note that a satisfying assignment should induce a set of groups and vice versa.

Hint: a non direct reduction (but you can start from there): Think about it as a covering problem. For example, it smells like the vertex-cover problem: each vertex $$v$$ defines a group of edges that touch $$v$$, and items can be the set of all edges.

• I'm not sure I understand that correctly. So there will be a vertex for each clause and same literals will be connected with edges? I do know how to reduce 3-SAT to k-vertex cover. Commented Jan 7 at 16:27
• A reduction from 3 sat to vertex cover is well known. I suggest you look it up. What I wanted to emphasize is that you should observe that an "assignment that satisfies all clauses" should correspond to "a subset of groups that covers all items". So somehow the reduction must take care of that. What I gave as a hint is a note that there is a well known reduction that already does the job. Commented Jan 7 at 16:34