# proving a problem is NP

Not what you're looking for? Search our solutions OR ask your own Custom question.

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 May 24, 2023, 12:48 pm ad1c9bdddfhttps://brainmass.com/math/graphs-and-functions/proving-a-problem-is-np-2338

#### Solution Summary

Proving a problem is NP is achieved.

$2.49