Question

Your friends’ preschool-age daughter Madison has recently learned to spell some simple words. To help encourage this, her parents got her a colorful set of refrigerator magnets featuring the letters of the alphabet (some number of copies of the letter A, some number of copies of the letter B, and so on), and the last time you saw her the two of you spent a while arranging the magnets to spell out words that she knows. Somehow with you and Madison, things always end up getting more elaborate than originally planned, and soon the two of you were trying to spell out words so as to use up all the magnets in the full set – that is, picking words that she knows how to spell, so that once they were all spelled out, each magnet was participating in the spelling of exactly one of the words. (Multiple copies of words are okay here; so for example, if the set of refrigerator magnets includes two copies of each of ‘C,’ ‘A,’ and ‘T,’ it would be okay to spell out "CAT" twice.) This turned out to be pretty difficult, and it was only later that you realized a plausible reason for this. Suppose we consider a general version of the problem of Using Up All the Refrigerator Magnets, where we replace the English alphabet by an arbitrary collection of symbols, and we model Madison’s vocabulary as an arbitrary set of strings over this collection of symbols.

Answer 1

See explaination

Step-by-step explanation:

Given a set U which is the set of magnets where each magnet representing a symbol, but are accepted more copies of the same symbol which we number arbitrarily 1,2,3,. ... For example if we had two copies of the symbol A, we would have elements A 1 ,A 2 ) and subsets S 1 ,...S n which represent words formed from the magnets that Madison knows how to spell. Note that if ‘’CAT” was a word in Madison’s vocabulary, then both of the sets C,A 1 ,T and C,A 2 ,T would appear among the S i . We are interested in the maximum number of disjoint sets (which correspond to words in Madison’s vocabulary that can be simultaneously spelled out by the magnet pieces).

We reduce Independent Set (IS) to Set Packing. Given an instance of IS ( G,k ), we set U to be the set of edges of G . For each vertex v i , we introduce a set S i = { e : e = ( v i ,x ) } which has one element for each edge incident to v i . We claim that G has an independent set of size k iff there are k disjoint sets among the S i . Indeed, if I is an independent set of size k then the k sets S v for v ∈ I have no common elements. Also, if { S i 1 ,...,S i k } are k disjoint sets then the vertices v i 1 ,...,v i k have no edges between them thus they form an independent set of size.