I have question already answered from past exam, and I'm trying to figure where my logic fails.

Given a graph find vertex cover of size 2. enter image description here

The question is how many variables are there going to be for the CNF when doing polynomial reduction for the input $\langle G,2 \rangle$ to SAT? specify those variables.

The answer given is : $X11$ $X12$ $X13$ $X14$ $X15$ $X16$ $X21$ $X22$ $X23$ $X24$ $X25$ $X26$

I didn't understand the answer. I tried to follow the logic from this thread: Reduce Vertex cover to SAT

But the answers do not seem to correlate.

Following the thread: Each node receives a certain $x_i$ marking whether or not the node is part of the $VC$. My nodes are $v_1$ and $v_6$ for vertex cover so its corresponding $x_i$ has the value $1$. other variables have $x_i$ with value $0$. For each edge in the graph presenting the clause $\left \{ x_i\vee x_j \right \}$. This is the part where I get a different answer : I get $X_{12}$ $X_{13}$ $X_{14}$ $X_{15}$ $X_{16}$ $X_{56}$ which is completely different answer from what was given... I tried to search the web but the thread is the best reference I could find(it seemed the most identical..). What is the problem with my way of solving?

  • $\begingroup$ There is no single reduction from vertex cover to SAT. Perhaps the answer refers to a different reduction? $\endgroup$ Oct 2 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.