CMI2018-A-9

Question

Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multi-talented and each individual has the skills to take part in a subset of the events. However, the same individual cannot be part of the team for two different events because of a possible clash in timings. Your aim is to create teams to take part in as many events as possible.

To do this, you decide to model the problem as a graph where the nodes are the events and edges represent pairs of events where the team that you plan to send shares a member. In this setting, the graph theoretic question to be answered is:

• A. Find a maximum length simple cycle
• B. Find a maximum size independent set
• C. Find a maximum matching
• D. Find a maximal connected component

Answer 1

$\mathbf{\underline{Answer:\Rightarrow (b})}$

$\mathbf{\underline{Explanation:\Rightarrow }}$

As all the students are multi-talented, then we do want most of them to participate so as to maximize the gain, and also because each individual has the skills to take part in the subset of events.

So, we just have to calculate the maximum independent set for this problem where the nodes represent the events and edges represent the pair of events, when the above situation is represented graphically.