# Reducing MAX-2SAT to Vertex Cover?

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.

## 1 Answer

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

• 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. – Paradox Aug 1 '16 at 15:56
• 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. – Tom van der Zanden Aug 1 '16 at 17:18