Question

Your friends are involved in a large-scale atmospheric science experiment. They need to get good measurements on a set S of n different conditions in the atmosphere (such as the ozone level at various places), and they have a set of m balloons that they plan to send up to make these measurements. Each balloon can make at most two measurements.

Unfortunately, not all balloons are capable of measuring all conditions, so for each balloon i = 1, ..,..,m, they have a set S_i of conditions that balloon i can measure. Finally, to make the results more reliable, they plan to take each measurement from at least k different balloons. (Note that a single balloon should not measure the same condition twice.) They are having trouble figuring out which conditions to measure on which balloon.

Example. Suppose that k = 2, there are n = 4 conditions labeled q, c2, c3, c4, and there are rn = 4 balloons that can measure conditions, subject to the limitation that S~ = Sz = {q, c2, c3}, and $3 = $4 = {q, q, c4}..Then one possible way to make sure that each condition is measured at least k = 2 times is to have

¯ balloon I measure conditions

¯ balloon 2 measure conditions cz, cs,

¯ balloon 3 measure conditions q, c4, and

¯ balloon 4 measure conditions c~, c4.

(a) Give a polynomial-time algorithm that takes the input to an instance of this problem (the n conditions, the sets Si for each of the ra balloons, and the parameter k) and decides whether there is a way to measure each condition by k different balloons, while each balloon only measures at most two conditions.

(B). You show your friends a solution computed by your algorithm from (a), and to your surprise they reply, "This won’t do at all--one of the conditions is only being measured by balloons from a single subcontractor." You hadn’t heard anything about subcontractors before; it turns out there’s an extra wrinkle they forgot to mention ....

Each of the balloons is produced by one of three different sub. contractors involved in the experiment. A requirement of the experiment is that there be no condition for which all k measurements come from balloons produced by a single subcontractor.

For example, suppose balloon 1 comes from the first subcontractor, balloons 2 and 3 come from the second subcontractor, and balloon 4 comes from the third subcontractor. Then our previous solution no longer works, as both of the measurements for condition c~ were done by balloons from the second subcontractor. However, we could use balloons 1 and 2 to each measure conditions c1, c2, and use balloons 3 and 4 to each measure conditions c3, c4. Explain how to modify your polynomial-time algorithm for part (a) into a new algorithm that decides whether there exists a solution satisfying all the conditions from (a), plus the new requirement about subcontractors.