NP-completeness proofs (1): reduction from 3-SAT

14 Dec, 2024

This post gives you the proofs of the NP-completeness of several decision problems—independent set, clique, vertex cover, and vertex coloring (graph coloring). Instead of doing the easier reduction, let us do some brain exercise by reduction from 3-SAT today. 😎

Definition.

3-SAT: Given a 3-CNF formula of $k$ clauses, does there exist a set of values that makes the formula True?

In the following problems, I’ll also include example figures to demonstrate the construction of gadgets and edges. For consistency, the example formula to be used in all following proofs will be:

$(a\vee b\vee c)\wedge (\neg a\vee b\vee \neg c)$.

P1: Independent set

Definition.

Independent set decision problem: Given a graph $G(V,E)$ and an integer $k$, does there exist an independent set (i.e., a subset of vertices such that no pair of vertices have an edge between them) of size $k$?

Proof by reduction from 3-SAT.

1. Certificate: Iterating through all edges in the independent set and seeing if both ends are in the independent set, costing $O(|E|)$, which is in polytime. Thus, the problem is NP.

2. Reduction: Construct a graph $G$ by the following steps:

   (1) For each clause, create vertices representing literals in the clause, then connect them to form a “triangle gadget.”

   (2) Connect all pairs of vertices representing complementary literals in step (1).

   Given an algorithm to find an independent set $S$ of size $k$ in $G$, no pairs of complementary literals will be in $S$, and no two literals in the same “triangle gadget” (clause) will be in $S$. Since $S$ has a size of $k$ and there are $k$ “triangle gadgets,” one and only one literal in each clause will be in $S$. By setting them to True, we can get a solution of 3-SAT.

   

   Example of black “triangle gadgets” in step (1), and red edges in step (2).

3. Construction of the “triangle gadgets” costs $O(k)$, and iterating through all complementary literals costs at most $O(k^2)$, both are in polytime. In conclusion, the independent set problem is NP-complete.

P2: Clique

Definition.

Clique decision problem: Given a graph $G(V,E)$ and an integer $k$, does there exist a clique (i.e., a subset of vertices such that every two distinct vertices in the clique are adjacent) of size $k$?

Proof by reduction from 3-SAT.

1. Certificate: Iterating through all vertices in the clique and their edges would cost $O(|V|\cdot |E|)$, which is in polytime. Thus, the problem is NP.

2. Reduction: Let there be $n$ variables and $k$ clauses in this 3-SAT. Construct a graph $G$ by the following steps:

   (1) For each clause, construct a “triangle gadget” with each vertex representing a literal in the clause.

   (2) For all “triangle gadgets” constructed in step (1), connect all pairs of nodes in different “triangle gadgets” except for pairs $(a,\neg a)$.

   Given an algorithm to find a clique of size $k$, only one literal of each clause could be in the clique, and for each variable, $a$ and its negation $\neg a$ would not be both in the clique. By setting all literals in the clique True, we can get a solution to the 3-SAT formula.

   

   Example of black “triangle gadgets” in step (1), and red edges in step (2).

3. Constructing the “triangle gadgets” costs $O(k)$, connecting the triangles costs $O(k^2)$, both of which are in polytime. In conclusion, the clique decision problem is NP-complete.

P3: Vertex cover

Definition.

Vertex cover decision problem: Given a graph $G(V,E)$ and an integer $k$, does there exist a subset of vertices $S\subseteq V$ such that $|S|\le k$ and for each edge $(u,v)\in E$, at least $u$ or $v$ belongs to $S$?

Proof by reduction from 3-SAT.

1. Certificate: Calculating $|S|$ costs $O(|V|)$, and verifying all edges costs $O(|E|)$, both in polytime. Thus, the problem is NP.

2. Reduction: Let there be $n$ variables and $k$ clauses in this 3-SAT. Construct a graph $G$ by the following steps:

   (1) For each clause, construct a “triangle gadget” with each vertex representing a literal in the clause.

   (2) For each variable $a$ and its negation $\neg a$, construct a connected “pair gadget” of vertices for them.

   (3) Connect $a$ in pairs to $a$ in the “triangle gadgets.”

   

   Example of black “triangle gadgets” in step (1), blue “pair gadgets” in step (2), and red edges in step (3).

   A vertex cover of $G$ must contain at least $n$ vertices to cover the “pair gadgets,” and at least $2k$ vertices to cover the “triangle gadgets.” Given an algorithm to find a vertex cover of size $n+2k$, this vertex cover must have exactly one literal in each “pair gadgets” (set to True), and exactly two literals in each “triangle gadgets” (set to False) to be able to satisfy $n+2k$ size. Therefore, from this vertex cover, we know that we can make the 3-SAT formula satisfy by setting which literals to True, solving the 3-SAT problem.

3. The construction of $G$ is $O(n+k)$, thus the reduction is in polytime. In conclusion, the vertex cover decision problem is NP-complete.

P4: Vertex coloring (graph coloring)

Definition.

$k$-coloring: Given a graph $G(V,E)$ and an integer $k$, does there exist a proper vertex coloring (i.e., no two vertices sharing the same edge have the same color) using at most $k$ colors?

For simplicity, here I’ll just use 3-coloring to demonstrate the gist of this reduction.

Definition.

3-coloring: Given a graph $G(V,E)$, does there exist a proper vertex coloring using at most 3 colors?

Proof of 3-coloring by reduction from 3-SAT.

1. Certificate: Verifying all vertices and their edges would cost no more than $O(|V|\cdot |E|)$, which is in polytime. Thus, the problem is NP.

2. Reduction: Let there be $n$ variables and $k^{\prime }$ clauses in this 3-SAT. Construct a graph $G$ by the following steps:

   (1) Construct a “base triangle gadget” of vertices representing True, False, and Base. In a 3-coloring, this “base triangle gadget” will be painted in all 3 different colors.

   (2) For each variable $a$ and its negation $\neg a$, construct a connected “pair gadget” of vertices for them, then connect both vertices to the Base:

   

   Example of black “base triangle gadget” in step (1), and blue “pair gadgets” in step (2).

   In a 3-coloring, one of the $a$ and $\neg a$ will be colored True, and the other False. This ensures that complementary literals will not be True at the same time.

   (3) For each clause, create two “triangle gadgets” of vertices, then connect them to corresponding literals in step (2) and the “base triangle gadget” in step (1) in the following way:

   

   Example of black “triangle gadgets” and red edges connecting them to the previous gadgets.

   If $a$, $b$, and $c$ are all False, by this design, the vertex representing $a\vee b$ will be False, then $a\vee b\vee c$ will be False, and finally, violating coloring rules since $a\vee b\vee c$ has to be True. This design, in addition to step (2), ensures that at least one of $a$, $b$, and $c$ has to be True.

   

   Example of the final graph. “Pair gadgets” are rendered blue, “base triangle gadget” and other “triangle gadgets” are rendered black, and the edges connecting different gadgets are rendered red.

   Given an algorithm to find a solution to 3-coloring of $G$, we can directly get a solution to 3-SAT.

3. Construction of the “pair gadgets” in step (2) costs $O(n)$, and construction of the “triangle gadgets” in step (3) costs $O(k^{\prime })$, both of which are in polytime. In conclusion, the 3-coloring is NP-complete.

#Algorithms