# CLIQUE $\leq_p$ SAT

i'm trying to reduce CLIQUE to SAT:

• Given: Graph G=(Vertices V, Edges E) and $$k \in \mathbb{N}$$
• Output: Formular F such that if G contains a complete subgraph of size k, the formular is satisfiable (and vice versa).

I tried doing it the way Cook/Levin showed that SAT is NP-complete by introducing a set of booleans $$v_i$$ for each vertex and $$e_{i, j}$$ for an edge going from $$v_i$$ to $$v_j$$. Now if $$v_i$$ is part of the clique, then $$e_{i, j}$$ must be true iff $$v_j$$ is also in the clique.

So we can conclude, that $$v_i \land v_j \implies e_{i, j}$$ and this is for true for at least $$i, j \in \{0, ..., k - 1\}$$ and $$i \neq j$$. Also we need to make sure that no edge that doesn't exist can be set to true: $$\bigwedge_{(i, j)\notin E} \lnot\, e_{i, j}$$.

I don't know if im on the correct way or if I might miss something.

1. How would I restrict the formular $$v_i \land v_j \implies e_{i, j}$$ to be true for at least k variables?
2. Is this way in poly-time?
3. Is there any better way?
• Is there a particular reason you are trying to reduce clique to SAT and not the other way around? Assuming your goal is establishing NP-completeness of clique, usually one proves it by showing clique is in NP (a rather trivial matter) followed by establishing a reduction from 3SAT to clique (using appropriate graph gadgets). – dkaeae Aug 13 '19 at 14:21
• Also note that, although not very enlightening, you can achieve what you want by constructing an NTM for clique and then using the construction from the Cook-Levin theorem on said NTM. This might be the fastest (or laziest) way of obtaining the reduction. – dkaeae Aug 13 '19 at 14:24
• Yes I know that for normal people do it the other way around. I was just trying to challenge me as in a video i was watching the it said that the way CLIQUE <= SAT is easy to show. Constructing a NTM is easy indeed! I was just trying to exercise my reduction skills! – gxor Aug 13 '19 at 15:21

There are many ways to reduce CLIQUE to SAT. Probably the simplest is as follows. Suppose that we have a graph $$G = (V,E)$$, and interested in a $$k$$-clique. We will have $$k|V|$$ variables $$x_{iv}$$, whose intended meaning is "the $$i$$th vertex of the clique is $$v$$". The constraints are:
• There is an $$i$$th vertex: for all $$1 \leq i \leq k$$, $$\bigvee_{v \in V} x_{iv}$$.
• The $$i$$th and $$j$$th vertices are different: for all $$1 \leq i < j \leq k$$ and $$v \in V$$, $$\lnot x_{iv} \lor \lnot x_{jv}$$.
• Any two vertices in the clique are connected: for all $$1 \leq i < j \leq k$$ and $$v,u \in V$$ such that $$(v,u) \notin E$$, $$\lnot x_{iv} \lor \lnot x_{ju}$$.