Conflict Detection Algorithm

Question

I have been trying to come up with a better algorithm that detects conflicts in the scenarios below.

Let's say we have 4 dancers. We pair them up and find out which ones can dance together. So, we have the dancer # combination and whether they can dance together or not.

(1,2) True
(1,3) True
(1,4) False
(2,3) True
(2,4) False
(3,4) False

At the end of the day, I want to know which group of dancers I can group together.

A group can only be formed when all of the dancers within the group can dance with each other AND no dancer outside the group can dance with any dancer in the group.

For example, group A can be formed with dancers {1,2,3} because they call can dance with each other (i.e. (1,2), (2,3), and (1,3) are True) AND no dancer outside the group can dance with them (i.e. 4 is outside the group and (1,4),(2,4),(3,4) are all false).

Now, if we change:

(2,4) -> True

grouping changes quite a bit. I can no longer group 1,2 and 3 together because even though (1,2), (1,3) and (2,3) are all True, there is a dancer (#4) that can dance with 2 (i.e. (2,4) is True).

Now, can we group 1 and 3? No. Even though (1,3) is True, there would be one dancer outside the group that CAN dance with either 1 or 3 (i.e. (2,3) and (1,2) are True).

I came up with an algorithm that simply uses some non-sophisticated logic, but I was wondering if one can frame this problem in terms of a CS or Math problem, and whether something similar has been formally solved already.

If it helps you visualize this, you can draw rectangles or circles where they overlap if they can dance together.

Answer 1

Your dancers are vertices of a graph, and there is an edge between two dancers if they are compatible. A set of dancers is a component if there's what you might call a "chain of compatibility" between every pair of them: that is, every pair of dancers is either compatible or you can come up with a sequence such as "Alice is compatible with Bob, Bob is compatible with Charlotte and Charlotte is compatible with Daniel" to get between them. A group of dancers who are all compatible with each other are a clique.

What you're looking for is a component that is also a clique. These are easy to find because you can use a greedy strategy. Suppose we want to know if a particular dancer (say, Alice) is in one of these groups. We grow a set of dancers as follows. Initially, the set is just Alice. Then, we keep adding dancers to the set if they're compatible with anybody inside the set. When we can't add anyone, we've found the component. So now, we just need to check that the component is a clique: that is, everybody within the component is compatible with everybody else.

You can do this more efficiently by checking for being a clique as you add new dancers. Again, start with just Alice. Then define a set of newcomers to be all people who are compatible with somebody in the set we've built so far. If any of those people are incompatible with each other or with somebody who's already in the set, Alice isn't part of a group; otherwise, add all the newcomers to the set and select the next set of newcomers.