Explore BrainMass

Explore BrainMass

    proving a problem is NP

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

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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 ad1c9bdddf


    Solution Summary

    Proving a problem is NP is achieved.