Accommodate maximum peoples in tour

I have to arrange a tour. There are N peoples who want to attend the tour. But some of them are enemies with each other. (enemy of enemy may or may not be your enemy. If A is enemy of B, B is also enemy of A) If I accommodate a person in my tour, I can not accommodate his enemy.

Now I want to accommodate maximum possible number of persons in the tour. How can I find this number?

ex: If there are 5 tourists, and let's call them A-E. A is enemy with B and D, B is enemy of E, and C is enemy of D.

   A    B   C   D   E
  +---+---+---+---+---+
A | - | X |   | X |   |
  +---+---+---+---+---+
B | X | - |   |   | X |
  +---+---+---+---+---+
C |   |   | - | X |   |
  +---+---+---+---+---+
D | X |   | X | - |   |
  +---+---+---+---+---+
E |   | X |   |   | - |
  +---+---+---+---+---+

In this case following trips are possible: empty, A, B, C, D, E, AC, AE, BC, BD, ACE, CE, DE etc. Out of these, best tour is ACE as it accommodates 3 tourist and hence the answer 3.

My approach:

• I tried looping and trying combinations with bitmaps, but they are very slow.
• I am currently using DFS but trying to find even a better method.
• I tried to work by creating friendship graph and prepare some
  spanning tree. But it doesn't work as A can travel with B and B can
  travel with C does not guarantee A and travel with C.
• I tried by creating enemity graph and finding some weak links but ended up clueless.

I would be thankful, if somebody can give me a hint or point to a good resource to solve this problem.

Create a graph from the tourists :

• each node is a tourist
• if two tourists are enemies draw an edge between them
• find the maximum independent set

There are very well detailed algorithms for finding maximum independent set in this paper: Algorithms for Maximum independent Sets

And a parallel approach has been provided in this one:Lecture Notes on a Parallel Algorithm for Generating a Maximal Independent Set

And this is a java implementation.