# NP Complete Problems

Karp’s paper

We cover a couple of reductions from Karp’s paper here.

NODE COVER is reducible to SET COVERING

NODE COVER:

Input: Graph $G$, positive integer $l$

Property: There is a set $R \subseteq V$ such that $|R| \le l$ and every edge is incident with some node in $R$

SET COVERING:

Input: Finite family of finite sets $\{S_j\}$, a positive integer $k$

Property: There is a subfamily $\{T_h\} \subseteq \{S_j\}$ containing $\le k$ sets such that $\bigcup T_h = \bigcup S_j$

Given an instance of NODE COVER $(G = (V,E), l)$, we will construct an instance of SET COVERING $(\{S_j\}, k)$ as follows:

$S_j =$ Set of edges incident with vertex $j \in V$ and $k = l$

Claim: $(G = (V,E), l) \in$ NODE COVER iff $(\{S_j\}, k) \in$ SET COVERING

Proof: The reduction maps vertices of the graph to sets of the family. Each set contains elements that corresponds to the edges in the original graph adjacent to the vertex represented by that set. If $(G = (V,E), l) \in$ NODE COVER, then $\exists$ $R \subseteq V$ such that $R \le l$ and every node in $V$ is incident with some node in $R$. Consider the subfamily $\{T_h\}$ for all $h \in R$. Then $\bigcup T_h = \bigcup S_j$ since every node in $V$ is incident with some node in $R$. Similarly, if $(\{S_j\}, k) \in$ SET COVERING, then there exists a subfamily $\{ T_h \}$ such that $\bigcup T_h = \bigcup S_j$. Let $R$ be the index set of the subfamily $\{T_h\}$ in $\{S_j\}$. Then $|R| = l$ and every node in $V$ is incident on some node in $R$ since $\bigcup T_h = \bigcup S_j$.

CNF-SAT is reducible to 3-SAT

CNF-SAT:

Input: disjunctive clauses $C_1, C_2, \dots, C_p$ each containing an arbitrary number of literals from the set $\{x_1, x_2, \dots, x_m\} \bigcup \{\overline{x_1}, \overline{x_2}, \dots, \overline{x_m}\}$

Property: The set $\{C_1, C_2, \dots, C_p\}$ is satisfiable

3-SAT:

Input: disjunctive clauses $D_1, D_2, \dots, D_r$ each containing at most 3 literals from the set $\{u_1, u_2, \dots, u_m\} \bigcup \{\overline{u_1}, \overline{u_2}, \dots, \overline{u_m}\}$

Property: The set $\{D_1, D_2, \dots, D_r\}$ is satisfiable

Given an instance of CNF-SAT $C_1, C_2, \dots, C_p$, we will construct an instance of 3-SAT $D_1, D_2, \dots, D_r$ as follows:

Replace a clause $(t_1 \vee t_2 \vee \dots \vee t_k)$ where $k > 3$ by two clauses $(t_1 \vee t_2 \vee u_1)$ and $( \overline{u_1} \vee t_3 \vee \dots \vee t_k)$, where $u_1$ is a new variable. Continue the process till all clauses have at most 3 literals per clause.

Claim: $C_1, C_2, \dots, C_p \in$ CNF-SAT iff $D_1, D_2, \dots, D_r \in$ 3-SAT

Proof: The constructed formula is logically equivalent to the original formula. To see why, observe that if $u_1$ is true, the new clauses are satisfiable iff $t_3 \vee \dots \vee t_k$ is true. If $u_1$ is false, the new clauses are satisfiable iff $t_1 \vee t_2$ is true. Thus, the new clauses are satisfiable iff $t_1 \vee t_2 \vee \dots \vee t_k$ is true, which is equivalent to the original clause. Thus, $C_1, C_2, \dots, C_p \in$ CNF-SAT iff $D_1, D_2, \dots, D_r \in$ 3-SAT.