Reduction 3SAT and CLIQUE

Question

Hello everyone this is my first question ever and I apologize if I ask in the wrong manner causing this post to be either closed or deleted. I'm learning Reductions and my professor has asked us to write a paper on reductions (3SAT)

When doing the Reduction from the Clique Problem to 3SAT, I understand that we make clauses and every clause contains 3 literals (hence, 3SAT) but my problem comes when choosing what literals and why they choose them. How do I know which literals to choose? So I know that in every clause I'll have x1, x2 and x3, but how do I choose their assignment order? In one clause I have (x1 or x2 or x3) and in another I have (x1 or not x2 or not x3). How were these chosen?

Also, it seems they don't begin with a graph in mind already. What if I'm given a graph to begin with, how would I convert it into x1, x2, x3? If for clause I have 3 vertices, how would I assign them their respected boolean expression? Thank you very much

Answer 1

Here is one possible way to reduce Clique to SAT (you can then further reduce it to 3SAT). This type of reduction is often used in (propositional) proof complexity, an area of complexity theory.

Given a graph $G = (V,E)$ and a number $k$, we will have variables $x_{iv}$ for every $1 \leq i \leq k$ and every $v \in V$. You should think of $x_{iv}$ as stating that $v$ is the $i$th vertex in the clique. We want to encode the following constraints:

1. For each $i$, there is an $i$th vertex in the clique: $\bigvee_{v \in V} x_{iv}$.

2. For each $i,j$, the $i$th vertex is different from the $j$th vertex: for each $v \in V$, $\lnot x_{iv} \lor \lnot x_{jv}$.

3. For each non-edge $(u,v) \notin E$, $u,v$ cannot both belong to the clique: for each $i,j$, $\lnot x_{iu} \lor \lnot x_{jv}$.

You can think of the second constraint as a special case of the third one.

If we take all these clauses together, we get a CNF which states that "the $x_{iv}$ encode a $k$-clique in $G$". This CNF is satisfiable iff $G$ contains a $k$-clique.

If you want to get a 3CNF, all you need to do is to convert the constraints of the first kind into 3-clauses. There is a standard way to do this: if the vertices are $v_1,\ldots,v_n$, we replace $\bigvee_{v \in V} x_{iv}$ with $$ x_{iv_1} \lor x_{iv_2} \lor y_{iv_2} \\ \lnot y_{iv_2} \lor x_{iv_3} \lor y_{iv_3} \\ \lnot y_{iv_3} \lor x_{iv_4} \lor y_{iv_4} \\ \ldots \\ \lnot y_{iv_{n-2}} \lor x_{iv_{n-1}} \lor x_{iv_n} $$ Here the $y_{iv}$ are new variables. This set of clauses is equivalent to the original clause $x_{iv_1} \lor x_{iv_2} \lor \cdots \lor x_{iv_n}$.

Answer 2

If you want to reduce Clique directly to 3SAT, you can design a boolean circuit, where the input is a graph and a subset of vertices, and the output is TRUE if that subset is a clique and FALSE otherwise.

If the graph has N vertices, you need:

• N variables, one for each vertex, which is TRUE if it is part of the subset and FALSE otherwise.
• N * (N - 1) variables, one for each pair of vertices, which is TRUE if they are connected, and FALSE otherwise.
• For each vertex, check that either it isn't part of the subset or it is connected to all vertices part of the subset (quadratic amount of operations, using ANDs and ORs). All the results must be ANDed together to produce the final decision bit.

Generally you want to specify things about the size of the clique. Therefore you need to perform binary addition to count the number of vertices that are in the subset (using the 0s and 1s in the input). Then you add any restrictions on the clique size with extra clauses.

If you don't know how to convert a boolean circuit to a list of 3SAT clauses then this should make you understand: for an AND gate where A & B = C, there are 8 different possibilities for ABC: 000, 001, 010, 011, 100, 101, 110, 111. But half of them are incorrect. For example 110 is incorrect because 1 & 1 = 1. So at least one of the bits should be different. Therefore you must add the clause (!A | !B | C).

Once you have found a satisfying assignment (good luck), read the 1s and 0s in the input part to extract the subset which is a clique.