# Reducing INDSET and MAXCUT to 3SAT

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.

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

$$\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.