Suppose we have a set $S$ of (fixed-size) graphs, many of which are isomorphic to each other. How do you find a minimum-size set $M$ of graphs such that every $g\in S$ is isomorphic to some graph in $M$? It would be nice to have a solution that's more efficient than running graph isomorphism $O(|S|^2)$ times.
If there isn't an efficient way, is there a way to get close? (i.e. find an approximation $M^*$ such that $|M^*| \sim |M|$ asymptotically, or something like that.)