-1
$\begingroup$

I have an example for a reduction of 3CNF to Clique, there is one thing I don't get about it, hopefully you could clarify it. The reduction works like this:

Construct a graph G = (V, E) as follows:

Vertices: Each literal corresponds to a vertex.

Edges: All vertices are connected with an edge except the vertices of the same clause and vertices with negated literals.

Why is it important that that negated literals will not be connected? How would that effect the reduction?

$\endgroup$
  • 2
    $\begingroup$ What do you think? What have you tried? Have you tried running the reduction by hand on a few sample problem instances (a few 3SAT instances) to see what would happen? We expect you to make a serious effort before asking. This question is one where you could easily discover the answer on your own by just trying a few examples. $\endgroup$ – D.W. Jan 31 '14 at 3:09
  • $\begingroup$ @D.W. I have tried, a none trivial 3CNF formula that can not be satisfied have 8 clauses, it not very easy to deduce what really happens there. $\endgroup$ – aviran Jan 31 '14 at 19:53
1
$\begingroup$

The goal of the reduction is to enforce the fact that a clique of the graph of size $|Clauses|$ is exactly a valid instanciation of the variables satisfying all clauses of the formula.

So by not connecting variables of the same clause together, you force a clique of size $|Clauses|$ to pick one variable in each clause, setting it to true.

However, you don't want this instanciation to contradict itself: you cannot have $x$ and $\neg x$ true at the same time. For instance the formula with two clauses $x\wedge \neg x$ should not be satisfiable. So you forbid a clique to contain a variable and its negation, by not connecting them together. Therefore, a clique has to be coherent, so it always represents a valid instanciation. Notice that it can be only a partial instanciation, in which case you can choose anything for the remaining variables.

$\endgroup$
1
$\begingroup$

What is meant, is that literals that are the negation of each other are not connected. The reason for this is that they cannot both be satisfied at the same time. (The idea of the reduction is, that the graph contains a clique containing nodes corresponding to one literal from each clause, exactly if all these literals can be satisfied at the same time.)

$\endgroup$
  • $\begingroup$ why does connecting negated literals from two different clauses will cause the formula to not be satisfied? different clauses might not be dependent on that literal, is this certain or just a precaution? $\endgroup$ – aviran Jan 30 '14 at 19:11
  • $\begingroup$ If the formula can be satisfied using other literals, then the nodes corresponding to those literals will form the clique. $\endgroup$ – FrankW Jan 30 '14 at 19:22

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.