Snow White and 7 Conference Rooms

Question

You are the chief algorithm officer for Snow White Inc.  Because of your algorithmic abilities, Snow White Inc. is very successful and has hundreds of thousands of investors.  You are planning the next investor conference.  You want to make sure that all investors who know each other attend the meeting in different rooms.  You are trying to decide if the 7 conference rooms in the Snow White Inc. head quarters will be sufficient or not.  Prove that this decision problem is NP-complete by using one of the known NP-complete problems (CLIQUE, 3-SAT, Hamiltonian Path, Hamiltonian Cycle, Coloring, Independent Set, etc.)

Answer 1

We can reduce 7 colouring to the 7 conference rooms problem. The graph nodes can be reduced to investors and the graph edges can be used to mark which investors know each other. If we are able to fit all the investors in 7 rooms that means that the graph can be represented using 7 colouring. Hence the graph has 7 colouring iff we can fit the investors in 7 rooms. Hence 7 rooms is as hard as 7 colouring and is NP Complete

Answer 2

Set this question as F.

Firstly, there are n people here and we need to divide the n people into 7 rooms. If there is a solution and we need to check whether it qualifies. There is a maximum of n people per room, we just need to check if they know anyone. If we use the adjacency matrix to store the relationships between people, it takes only O(n^2) time complexity to traverse through. Therefore, question F belongs to NP.

Secondly, Coloring question is known as a NP-complete problem.

Thirdly, there is an example show that we can reduce Coloring to F.

F: We set each person as a node and connect them if they know each other. In this situation, the relationships of all people can be stored in a graph.

In question Coloring, any two nodes of the same color cannot be adjacent to each other.

In F, any two people who know each other can be in a same room.

We create a graph like the relationships of F, and we tried to use 7 colors to paint the whole graph. If there is a solution the F can be solved, else it is not possible.

Above all, F reduces to Coloring question in polynomial time.