Algorithm to find the optimal group of compatible elements

Question

I have a set of entities and I need to group this entities in groups called specie. The set of all species defined calls Universe and an entity must belong to one and only one specie. For this I have a boolean intransitive function called f that returns if two entities, passed by parameters, are compatible. A specie is defined by a group of entities compatibles with each other and a universe is defined by a group of species that are not entirely compatibles with each other, assuming that the compatibility of two species is defined by the compatibility of all of it's entities.

How can I determine the universe that contains the smallest number of species possible for a given set of entities?

I tried as follows and my function returns a valid universe but not the one with the smallest number of species possible.

public class Specie {
    private List<Entity> individuals;

    public Specie() {
        this.individuals = new ArrayList<>();
    }

    public boolean matches(Entity e) {
        for (Entity s : this.individuals) {
            if (!f(s, e)) {
                return false;
            }
        }
        return true;
    }

    public void add(Entity i) {
        this.individuals.add(i);
    }
}

private static int numberOfSpeciesRecursive(List<Entity> entities, List<Specie> universe) {
    if (entities.size() == 0) {
        return 0;
    } else {
        List<Entity> remains = new ArrayList<>();
        Specie specie = new Specie();
        for (Entity e : entities) {
            if (specie.matches(e)) {
                specie.add(e);
            } else {
                remains.add(e);
            }
        }
        universe.add(specie);
        return 1 + numberOfSpeciesRecursive(remains, universe);
    }
}

Answer 1

Consider the entities as vertices of a graph, and add edges between vertices if the entities are compatible.

In this resulting graph, your definition of a species corresponds to the definition of a clique.

Therefore the problem of finding the minimum number of species is equivalent to covering the graph with the smallest number of cliques. This problem is known as minimum clique cover and is NP-complete.