I am looking at a combinatorial optimisation problem where I have N classes and k objects of each class.
Now I am looking for the optimal subset such that each of the N classes is represented exactly once. Not all objects can be combined with each other, e.g. object (N=1,k=1) might not be compatible with (N=2, k=4).
I can formulate this problem as looking for the maximal clique on a N-partite graph (but maybe there are other formulations that I'm not aware of). My question is whether an efficient algorithm exists for solving this problem.
This is known as the clique problem; it's hard and is in NP-complete in general, and yes there are many algorithms to do this.
If the graph has additional properties (e.g. it's bipartite), then the problem becomes considerably easier and is solvable in polynomial time
This implies that an efficient algorithm might exist for my problem, but I can't find it...