Greedy algorithm for the following

Question

I am trying to solve the following problem using Greedy Algorithm,

We have n friends and we want to give a present to each one of them. But we don't want to give the same present to two person who know each other. (if x knows y, then y knows x). People who do not know each other may take the same gift, it is okay. We want to minimize the number of distinct gifts given.

Here is what I thought, We try to make pairs of people who do not know each other, and give them all the same gift. But I am not sure whether this is a greedy algorithm. Also, we may want to find maximum group of people in which no one knows any other, so we can give hem the same gift. But can we do this? Can we find the maximum group of people who do not know each other?

Can anyone propose a greedy algorithm for the problem?

Answer 1

The problem you have mentioned is a restatement of Graph Coloring problem. You have to label the graph’s vertices with colors such that no two vertices sharing the same edge have the same color. The link given below is to the Greedy Coloring Algorithm.

http://en.wikipedia.org/wiki/Greedy_coloring

Answer 2

This is graph coloring problem, and greedy algorithm for it is straightforward:

a greedy coloring is a coloring of the vertices of a graph formed by
a greedy algorithm that considers the vertices of the graph in sequence
and assigns each vertex its first available color