Q25Single correct2 Marks7 Aug 2022

An IT convention is being organized in a fancy hotel. Many parallel sessions are planned. Each session has to take place in a separate hall. Sessions that do not overlap can share a hall. The organizer of the convention would like to know the minimum number of halls to reserve at the hotel to fit in all the sessions without any clashes. The organizer decides to model this as a graph where the nodes are the sessions and edges represent pairs of sessions with overlapping timings. In this setting, the graph theoretic question to be answered is:

A

Find a spanning tree with maximum number of edges.

B

Find a maximum size independent set.

C

Find a minimum size vertex cover.

D

Find a minimal coloring.