Reductions

Problem $A$ is said to reduce to $B$ if there exists a transformation $T:A\to B$ such that if an input $a\in A$ (gets accepted by $A$), then $T(a)\in B$ (also accepted by $B$ after transforming it via $T$). In addition, if $a\notin A$, then it must also be true that $T(a)\notin B$.

In other words, any inputs to $A$ that are accepted should be accepted by $B$ after transformation, and any inputs to $A$ that are rejected should also be rejected by $B$ after transformation.

Reducing boolean SAT to 3-SAT

We can now use boolean SAT and reduce it to any other NP problem to show that it is also NP-complete, like 3-SAT. We can represent boolean SAT as a circuit again. Then, we let every wire in the circuit correspond to a variable in the formula, and every gate in the circuit is represented as a clause.

For example, $w_1\text{ AND }{w}_2=w_3$ can be written as $(\neg w_3\vee w_1)\wedge (\neg w_3\vee w_2)\wedge (w_3\vee \neg w_2\vee \neg w_1)$.

Consider the following transformation: for every wire in the circuit, we assign it a new variable, and for every gate, we transform it into a clause.

• This can be done in linear time with respect to the circuit.
• The end result is a very, very long boolean formula of 3-CNF clauses.

Then, if we can find an assignment such that the boolean formula returns true, then we will also have found a combination of inputs such that the circuit returns true.

Reducing 3-SAT to independent set

The independent set of a graph $G=(V,E)$ is the set of vertices $S\subseteq V$ such that no two of which are adjacent. In other words, every edge $e\in E$ has at most one endpoint in $S$. Then, the problem is finding the independent set of $G$ of size $k$.

Transformation/construction

To reduce 3-SAT with $k$ clauses to this problem, we construct a graph $G$ such that choosing a vertex from $G$ corresponds to an assignment of true, and finding an independent set of size $k$ for $G$ satisfies the 3-SAT formula.

In particular, for each clause $C_1=(l_{i,1}\vee l_{i,2}\vee l_{i,3})$, we treat each variable as a separate node in the graph, and connect all three of them with edges.

Then, we also draw edges between these “triangle clusters” of vertices. In particular, if there exists another clause $C_n=(\neg l_{i,1}\vee l_{j,2}\vee l_{j,3})$ that uses the same variable $l_{i,1}$ from $C_1$ but negates it, then we connect these two vertices with an edge in the graph.

If there are $m$ clauses in the boolean formula, then there are $3m$ nodes in the graph. The size $k$ of the independent set of this graph is equal to $k=m$.

Proof of correctness

To prove the transformation is correct, we have to show that both ways are correct:

• If there exists a satisfying boolean assignment, this implies there exists a graph $(G,k)$ that has an independent set of size $\ge k=m$.
• If there is no satisfying boolean assignment, this implies $(G,k)$ does not have an IS of size $\ge k=m$.

We can only select one node per triangle cluster, otherwise we would be violating the IS rule. In addition, the same variables but negated are also connected with an edge. So, if it’s true in one triangle, it cannot be used in another triangle cluster (e.g. if it’s true in one clause it must be false in the other).

Since 3-SAT is NP-complete and can be reduced to independent set, this implies finding the independent set of a graph is also in NP-complete.

Reducing independent set to vertex cover

A vertex cover is a set $S\subseteq V$ of a graph $G=(V,E)$ such that every edge in the graph has at least one end point in $S$. To constrain the problem (because otherwise we would just all the vertices), the size of the set has to be less than $L$.

Now, consider a vertex cover $S$ for a graph. Since it covers all edges, at least one endpoint of every edge must be within $S$. We cannot have have an edge where both vertices are outside of $S$, because otherwise it’s not a vertex cover.

Then, the transformation is stupidly simple: consider the independent set and take its complement. We transform from the set of vertices where no vertices share a common edge to the complement of that, which by definition is a vertex cover.

Furthermore, we’re going from the maximal independent set to the minimal vertex cover. If the IS is of size $k$, then we have $L=n-k$.