proving a problem is NP
Please see the attachment below for the complete question.
We need to prove that the problem is NP -complete by reduction from Vertex-cover.
Problem :- Given a collection of sets { S1, S2 ,..., Sn} and a positive integer K. Does there exist a set T with at most K elements such that T disjoint Si not-equalto empty , 1<=i<=n ?
[we can use the edges in graph to create the sets in the collection ]
© BrainMass Inc. brainmass.com February 24, 2021, 2:06 pm ad1c9bdddfhttps://brainmass.com/math/graphs-and-functions/proving-a-problem-is-np-2338
Solution Summary
Proving a problem is NP is achieved.
$2.19