6. The Set Packing problem is: Given a set U of n elements, a collection S₁,..., Sm of subsets of U, and a number k, does there exist a collection of at least k of these sets with the property that no two of them intersect? Prove that the set packing problem is NP-complete. Here is an example where the Set Packing problem can arise. Imagine that you have a set U of n non-sharable resources, and a set of m software processes. The ith process requires the set S CU of resources in order to run. Then the Set Packing Problem seeks a large collection of these processes that can be run simultaneously, with the property that none of their resource requirements overlap (i.e., represent a conflict). 7. The subgraph isomorphism problem takes two undirected graphs G₁ and G2, and it asks whether G₁ is isomorphic to a subgraph of G2. (That is, whether by deleting certain vertices and edges of G2 we obtain a graph that is, up to renaming of vertices, identical to G₁.) Show that the subgraph isomorphism problem is NP-complete.
6. The Set Packing problem is: Given a set U of n elements, a collection S₁,..., Sm of subsets of U, and a number k, does there exist a collection of at least k of these sets with the property that no two of them intersect? Prove that the set packing problem is NP-complete. Here is an example where the Set Packing problem can arise. Imagine that you have a set U of n non-sharable resources, and a set of m software processes. The ith process requires the set S CU of resources in order to run. Then the Set Packing Problem seeks a large collection of these processes that can be run simultaneously, with the property that none of their resource requirements overlap (i.e., represent a conflict). 7. The subgraph isomorphism problem takes two undirected graphs G₁ and G2, and it asks whether G₁ is isomorphic to a subgraph of G2. (That is, whether by deleting certain vertices and edges of G2 we obtain a graph that is, up to renaming of vertices, identical to G₁.) Show that the subgraph isomorphism problem is NP-complete.
Related questions
Question
Please answer both questions in the screenshot provided.
Transcribed Image Text:6. The Set Packing problem is: Given a set U of n elements, a collection S₁,..., Sm of subsets
of U, and a number k, does there exist a collection of at least k of these sets with the property
that no two of them intersect? Prove that the set packing problem is NP-complete.
Here is an example where the Set Packing problem can arise. Imagine that you have a set
U of n non-sharable resources, and a set of m software processes. The ith process requires
the set S CU of resources in order to run. Then the Set Packing Problem seeks a large
collection of these processes that can be run simultaneously, with the property that none of
their resource requirements overlap (i.e., represent a conflict).
7. The subgraph isomorphism problem takes two undirected graphs G₁ and G2, and it asks
whether G₁ is isomorphic to a subgraph of G2. (That is, whether by deleting certain vertices
and edges of G2 we obtain a graph that is, up to renaming of vertices, identical to G₁.) Show
that the subgraph isomorphism problem is NP-complete.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
