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

**NODE COVER is reducible to SET COVERING**

**NODE COVER:**

Input: Graph , positive integer

Property: There is a set such that and every edge is incident with some node in

**SET COVERING:**

Input: Finite family of finite sets , a positive integer

Property: There is a subfamily containing sets such that

Given an instance of NODE COVER , we will construct an instance of SET COVERING as follows:

Set of edges incident with vertex and

Claim: NODE COVER iff 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 NODE COVER, then such that and every node in is incident with some node in . Consider the subfamily for all . Then since every node in is incident with some node in . Similarly, if SET COVERING, then there exists a subfamily such that . Let be the index set of the subfamily in . Then and every node in is incident on some node in since .

**CNF-SAT is reducible to 3-SAT**

**CNF-SAT:**

Input: disjunctive clauses each containing an arbitrary number of literals from the set

Property: The set is satisfiable

**3-SAT:**

Input: disjunctive clauses each containing at most 3 literals from the set

Property: The set is satisfiable

Given an instance of CNF-SAT , we will construct an instance of 3-SAT as follows:

Replace a clause where by two clauses and , where is a new variable. Continue the process till all clauses have at most 3 literals per clause.

Claim: CNF-SAT iff 3-SAT

Proof: The constructed formula is logically equivalent to the original formula. To see why, observe that if is true, the new clauses are satisfiable iff is true. If is false, the new clauses are satisfiable iff is true. Thus, the new clauses are satisfiable iff is true, which is equivalent to the original clause. Thus, CNF-SAT iff 3-SAT.