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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s