It assesses the learning outcome:

Understand the common complexity classes.

A workshop organiser is trying to distribute people into groups so that no group has two people who have previously worked together. There's a limit on the number of groups that can be created because each group will be in a separate room. The organiser knows who has worked with whom. Can she distribute the participants as required? The general problem is as follows.

Function:$$workshop groups

Input: people, an undirected graph; number of groups, an integer

Preconditions: people has n $>=2$ nodes; number of groups n

Output: ok$,$ a Boolean

Postconditions: ok is true if and only if the set of nodes of people can be divided into number of groups subsets so that neighbouring nodes are in different subsets.

Here is an example graph, with nodes representing people and edges representing work relations.

If number of groups is $1,$ then ok $=$ false, because the $5$ people can$$t be put in the same group. However, for number of groups $=3,$ ok is true: A and C are one group; E and B are another; and D is the third group. Another possible grouping would be A and E are the first group, C and D are the second, and B is the third.

Prove that this decision problem is in class NP by answering the following parts.

Q$1.$ Describe a certificate for a problem instance $($a graph$$people$$and an integer$$number of groups$)$ that has a true output. Give as example a certificate for the graph above and$$number of groups$=3.$

Q$2.$Explain why certificates for this problem can be verified in polynomial time. In other words, briefly explain what the verifier does, given$$people$,$number of groups$$ and the corresponding certificate, and why it takes polynomial time.