0
$\begingroup$

Given a graph and an integer $k$ is there an independent set larger than $k$ is INDSET problem and is there a cut larger that $k$ is the MAXCUT problem. Is there standard way to convert to 3SAT from these problems that preserves number of solutions? I have only seen reductions other way in standard texts. Since all these are NPC there should be a way to convert back.

$\endgroup$
1
  • 1
    $\begingroup$ The standard way is known as the Cook-Levin theorem, and it preserves the number of solutions. $\endgroup$ – Yuval Filmus May 15 '18 at 12:15
1
$\begingroup$

$\mathcal{INDSET}$ $\leq_p$ $\mathcal{3SAT}$:

For each vertex $v\in V$, create a Boolean variable $x_v$.

For each edge $uv\in E$, create a clause $\lnot x_u \lor \lnot x_v$

Now, to assure that there exist exactly (or more than) $k$ variables assigned to $\mathrm{TRUE}$, we need to sum over all the assigned value ($\mathrm{FALSE}$ as $0$, $\mathrm{TRUE}$ as $1$):

We use half-adder and full-adder. Note that each circuit gate using some Boolean operation like $C = A \oplus B$ can be transformed into $\mathcal{3SAT}$ clauses easily.

To compare the obtained sum and $k$, it is straightforward from their binary representations (as two arrays of Boolean variables), just scan from left to right (in big-endianness fashion).

$\mathcal{MAX-CUT}$ $\leq_p$ $\mathcal{3SAT}$:

For each vertex $v\in V$, create a Boolean variable $s_v$. A cut is then described by a partition of the vertex set $V=S\cup (V\setminus S)$, where $v\in S$ iff. $s_v=\mathrm{TRUE}$.

For each edge $e=uv\in E$, create a Boolean variable $c_e$ and some clauses to force that $c_e=(s_u\neq s_v)$. So, $c_e=\mathrm{TRUE}$ iff. $e$ is crossing $(S, V\setminus S)$.

Then, we use half-adder and full-adder as before to count the number of crossing edges. Lastly, compare as before.

$\endgroup$

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.