1
$\begingroup$

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?

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – popcorn
    Commented Jan 7 at 16:27
  • $\begingroup$ 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. $\endgroup$ Commented Jan 7 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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