4
$\begingroup$

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?
$\endgroup$
3
  • 2
    $\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, 2019 at 14:21
  • 2
    $\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, 2019 at 14:24
  • 1
    $\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, 2019 at 15:21

1 Answer 1

5
$\begingroup$

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}$.
$\endgroup$
5
  • $\begingroup$ thank you yuval so much! $\endgroup$
    – maya cohen
    Jun 21, 2022 at 11:25
  • $\begingroup$ but i still didnt understand , can you add a drawing ? of the reduction ? please $\endgroup$
    – maya cohen
    Jun 21, 2022 at 11:27
  • 1
    $\begingroup$ You will learn more by creating such a drawing yourself. $\endgroup$ Jun 21, 2022 at 11:29
  • $\begingroup$ i dont understand the notation x_iv what does it mean ? xiv, whose intended meaning is "the ith vertex of the clique is v" $\endgroup$
    – maya cohen
    Jun 21, 2022 at 11:45
  • 1
    $\begingroup$ It’s just the name of a variable. The variables are indexed by two indices, $i$ and $v$. $\endgroup$ Jun 21, 2022 at 11:46

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.