1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.