Question

Prove or disprove that INDEPENDENT-SET ?p SET-PACKING, that is, these two problems are computationally equally hard. Please use an illustration if it helps. The definitions of these two decision problems are summarized below. We already proved that INDEPENDENT-SET ?p SETPACKING, so assume this given.

- INDEPENDENT-SET: Given a graph G = (V, E) and an integer k, is there a subset of vertices such that $\left | S \right | \geq k$ and, for each edge in E, at most one - but not both - of its end nodes is in S?

AS C V

- SET-PACKING: Given a set U of elements, a set of subsets S1, S2, . . . , Sm of U, and an integer k, does there exist a set of at least k subsets that are pairwise disjoint (i.e., intersection = ? between every pair)?

Answer 1

Solution: Set Packing and Independent set e The input to INDEPENDENT SET is a graph G & a target number k, sets s1, s2... and target number k' is to be produced. . In independent set, each vertex would come with set of all incident edges & if two vertices have a common incident edge, then simulta- neous picking is not possible. as mon . For each of vertex vi, a set Si would contain exactly edges e that are incident on vi

. Hence, k' k is set and this reduction takes polynomial time. . For verification, first assume that G has an independent set of sizes at least k let it be T. Include Si with vi ET and construct C . size of C and T are equal, at most k = k. . The sets Si that is picked must be pairwise disjoint as no two vertices could share an edge. e Hence, a valid set packing of at least k sets is found . For opposite direction, assume that a new instance has size at least !k = k, and set packing C. . A vertex set T would consist exactly of those vi such that i € c . The size of T and C are same and is at most k e For an edge e, maximum one set Si would contain e such that maxi- mum of one node vi could be independent set of sizes at least k. . Hence, it proves that (G, k) was a true instance.