9-19: We Will Show Only Set Packing Is NP-Hard by the Following Reduction

Homework # 33 sample solution:

9-19: We will show only Set Packing is NP-hard by the following reduction:

Independent set £ P Set packing

Proof:

Given an instance of independent set (G, k), we construct an instance (S, C, k) of set packing that has k disjoint subsets.

Construction:

Given a graph and a target number k of independent set, we will generate the sets S1, S2, …… Sn, one for each vertex of G. If two vertices have an edge in common, they could not be selected into an independent set. Therefore, for each vertex vi of G, we create a set Si, containing the edges incident on vi. Since the size of independent set is k and we must also have k sets of edges. This reduction obviously runs in polynomial time. We can prove the following claim:

Claim: G has an independent set of size k iff (E, {S1, S2, …, Sn}) has a set of k mutually exclusive subsets.

The proof is omitted here.

9-23：

(1)  Does graph G have a simple path of length k?

Certificate: a path P

Certifier: We check if P is a simple path of G and has k+1 vertices.

This runs in linear time.

(2)  Is integer n composite?

Certificate : An integer t.

Certifier: boolean C(n, t) {

If gcd(n, t) > 1 return true else return false

}

Since gcd(x, y) take O(log(n)) time, so C(n,t) runs in polynomial time of O(log(n)).

(3)  Does graph G have a vertex cover of size k?

Certificate: a set V’ of vertices

Certifier: Boolean C(G, V’){

If (|V’| k) return false;

for each (u,v) in E if not(u in V’ or v in V’) return false

return true;

}

Certainly C(G, V’) runs O(k|E|) time, where G = (V, E), k <= |V|.