4
$\begingroup$

Is there a way of generating random isomorphic graphs for the purposes of testing tools like Nauty or BLISS? Every paper I've found says the authors had a database of certain isomorphic graphs, but I don't know how they constructed them or where I find test sets for graph isomorphism algorithms. I expect the answer to this question is no.

Is there a way to generate graphs that are likely to be isomorphic?

$\endgroup$
7
$\begingroup$
  1. create a graph $G = (V, E)$ as you like
  2. generate a random permutation $\sigma\in \mathfrak{S}(V)$, for example with Knuth's algorithm
  3. create the graph $G' = (V, E')$ where $E' = \{(\sigma(u), \sigma(v))\mid (u, v)\in E\}$
  4. Tada! $G$ and $G'$ are isomorphic!
$\endgroup$
1
  • 1
    $\begingroup$ You can also use this approach to create a graph pair which is almost isomorphic, by introducing small errors in the permutation. $\endgroup$
    – Discrete lizard
    Jan 5 at 8:17
4
$\begingroup$

While Nathaniel's response answered my question perfectly, part of my question also asked about where to find testsets for graph isomorphism algorithms. As such, I thought I'd start a list.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.