I am looking for an algorithm that could solve the problem stated below. Ideally, I am interested in an algorithm that would find the optimal solution (or one of them if it's non unique), but I'd be satisfied with a one providing only a good approximation? Thanks!
I did some web search but all I found was referring to either "graph labeling", "graph coloring", "connected-component labeling" problems, none of which seems to be relevant for my problem.
Statement: Given an undirected graph where vertices are labeled by a categorical variable, partition the nodes in groups such that:
- each group is a connected subgraph in the original graph,
- there isn't two nodes in a group with the same label,
- the number of groups is minimal.
Example: Given a social network where nodes are individuals and edges encode friendship, find the least number of groups such that:
- any two individuals in a group are related via a chain of friends in that group,
- no two individuals in the group have the same first name.
Variant: An interesting variant of it would consist in minimizing the number of edges that needs to be broken instead of the number of groups. In the example that would be the number of pair of friends that end up in two different groups.