In A simplified NP-complete MAXSAT problem, a reduction is given from Min Vertex Cover to MAX-2SAT by replacing each each vertex $x_i$ by a single-variable clause, and each edge by a two-variable clause:

\begin{align} \Phi = \left(\bigwedge_{i=1}^n x_i\right) \wedge \left(\bigwedge_{\lbrace i,j\rbrace \in E} (\overline{x}_i \vee \overline{x}_j)\right) \end{align}

This basically makes sense to me, because the QUBO version of Vertex Cover is to maximize: \begin{align} L = \sum_{i=1}^N x_i - \sum_{\lbrace i,j\rbrace \in E} x_ix_i \end{align} and QUBO can be converted to MAX-2SAT quite simply.

However, I would to know how the reverse transformation works.

How do you go from MAX-2SAT to Vertex Cover?

I don't actually know if this is an unsolved problem or not, but I figure it shouldn't be since they are both NP-Complete. Would it be as simple/tedious as trying to force an arbitrary MAX-2SAT instance into the same form as $\Phi$? I don't know if that can be done though.


You can reduce MAX-2SAT to Satisfiability (using Cook-Levin), which can then be reduced to Vertex Cover (Folklore).

  • $\begingroup$ I've seen 3-SAT -> Max-2SAT, but it's the reverse direction I'm having trouble with. Just like how Vertex Cover -> Max-2SAT seems easier than the reverse direction. $\endgroup$ – Paradox Aug 1 '16 at 15:56
  • $\begingroup$ The reverse direction is a consequence of the Cook-Levin theorem. It's not very pretty, but it gives you a way to construct the reduction. You build a TM to solve Max-2SAT, then pass that to the Cook-Levin reduction. $\endgroup$ – Tom van der Zanden Aug 1 '16 at 17:18

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.