# Is there an efficient way to reduce a set of graphs under isomorphism?

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.)

• – Chao Xu Dec 26 '18 at 8:59