2
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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, 2016 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, 2016 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.