Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

You are preparing a banquet where the guests are government officials from many different countries. In order to avoid unnecessary troubles, you are asked to check the list of international conflicts in the last ten years. Then, you will assign the guests to two tables, such that in each table, any two guests are not from countries that had conflicts in the last ten years.

Provide an efficient algorithm that determines whether it is possible to make such an assignment. If it is possible to do so, the algorithm should return the assignment of these two tables. What is the running time?

so I guess it asks here that a country can have conflicts with multiple countries and any two guests in the same table should not come from countries that had conflicts in the last ten years.

So lets say there are X number of people in the table then X-2 have conflicts with each other?

Also what algorithm would I use for this, can someone please help me out.

share|improve this question
    
A question like this is better suited on cs.stackexchange.com –  Millardo Peacecraft Apr 3 at 20:45
    
Have you ever heard of a hypergraph and a $k$-coloring of a hypergraph? –  Jared Apr 3 at 20:47
    
Never mind, you don't need a hypergraph, a regular graph would do (the edges would represent conflicts). You then need to find the chromatic number: en.wikipedia.org/wiki/Graph_coloring#Vertex_coloring of the resulting graph where you represent each official with a vertex and each conflict as an edge connecting two vertices (two officials) and the colors represent the different tables. If the chromatic number is $\leq 2$ then it's possible, otherwise it is not. –  Jared Apr 3 at 21:01
    
This particular problem probably can be solved efficiently (because it's attempting to find a $2$-coloring of a graph). However finding the chromatic number of a graph is, I believe, NP-Complete. So if the question was find the minimum number of tables, then you probably couldn't find an efficient algorithm. –  Jared Apr 4 at 0:05

1 Answer 1

up vote 2 down vote accepted

The following procedure should do the trick. It returns false if it is not possible to seat people and true otherwise. It also seats people as a side-effect:

While (not all persons seated){ 
  put a standing person p in the queue
  level(p)=0
  While (queue not empty){
    remove person p from the queue
     seat p at table (level(p) mod 2) + 1
     for all standing people r conflicting with person p{
       add r to the queue
       level(r)=level(p)+1
    }
  }
}
for all conlicts c {
  if people of the conflict seat at the same table{
     return false
  }
}
return true

If $X$ is number of people and $C$ is number of conflicts, the running time will be $\mathcal{O}(X+C)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.