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?
  • 1
    $\begingroup$ 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). $\endgroup$ – dkaeae Aug 13 '19 at 14:21
  • 1
    $\begingroup$ 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. $\endgroup$ – dkaeae Aug 13 '19 at 14:24
  • $\begingroup$ 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! $\endgroup$ – 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}$.

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.