Reduction: 3SAT → Independent Set

In 3SAT the input is a set of clauses, each with three or fewer literals, e.g.

Goal: Find a satisfying truth assignment.

In INDEPENDENT SET the input is a graph and a number $g$, and the problem is to find a set of $g$ pairwise non-adjacent vertices.

How do we transform this problem:

• Represent a clause $(x \vee \bar{y} \vee z)$ by a triangle with vertices labeled $x, \bar{y}, z$.
  • We choose a triangle because it has three vertices maximally connected, and forces us to pick only one of them for the independent set
  • A clause with two literals will be represented simply by an edge joining the literals
  • A clause with one literal can be removed in preprocessing step
  • Repeat this construction for all clauses

• To force exactly one choice from each clause, take goal $g$ to be the number of clauses

• To present from choosing opposite literals, put an edge between any two vertices that correspond to opposite literals

Recovering a solution

• If the graph has independent set solutions
  • Given an independent set $S$ of $g$ vertices in $G$, it is possible to efficiently recover a satisfying truth assignment to $I$.
  • For any variable $x$, the set $S$ cannot contain vertices labeled both $x$ and $\bar{x}$, because any such pair of vertices is connected by an edge.
  • Assign $x$ a value of true if $S$ contains a vertex labeled $x$, otherwise ($S$ contains vertex $\bar{x}$), assign $x$ to false.
  • Since $S$ has $g$ vertices, it must have one vertex per clause, it must have one vertex per clause.

• If graph $G$ has no independent set of size $g$, then the boolean formula is unsatisfiable
  • We’ll prove the contrapositive: If $I$ has a satisfying assignment then $G$ has an independent set of $g$.
  • For each clause, pick any literal whose value under the satisfying assignment is $true$, and add the corresponding vertex to $S$.