I was wondering if anybody knows where I can find some information about the current (practical) algorithms for finding graph isomorphisms. I've joined the bandwagon and wrote my own which I would like to compare with the others.

  • $\begingroup$ Also, I came up with an algorithm for computing chromatic polynomials that has a better running time than that employed by MATLAB's MuPad notebook. This is on account of better average branching of my algorithm. Do you have any suggestions of chromatic polynomial computation algorithms with which I can compare my algorithm? $\endgroup$ – Victor Rielly Mar 26 '16 at 21:59

To be taken seriously as a competitor you should be able to perform well on at least some of the difficult graph classes collected by Adolfo Piperno.

  • $\begingroup$ I believe igraph has C implementation of bliss and vf2, (there is link in the other answer). $\endgroup$ – joro Mar 27 '16 at 11:11
  • $\begingroup$ Is any of these provably sub-exponential? Not asking if they are significantly faster than sub-exponential almost always. $\endgroup$ – joro Mar 27 '16 at 11:59
  • 1
    $\begingroup$ @joro: No, they are exponential in the worst case. $\endgroup$ – Brendan McKay Mar 27 '16 at 22:47
  • $\begingroup$ I'd also link the paper B. D. McKay, A. Piperno, Practical graph isomorphism, II, Journal of Symbolic Computation, 60, 94-112 (2014) for a recent comparison of these (except VF2, it seems). $\endgroup$ – Janne Kokkala Mar 30 '16 at 5:41
  • 2
    $\begingroup$ @Victor: Random graphs are too easy. A better way to seek false negatives is to take graphs from Piperno's collection and form two random relabellings of them. $\endgroup$ – Brendan McKay Apr 17 '16 at 23:17

To compare your implementation with others, I would recommend to benchmark it against sage,igraph and McKay's canonical labelling (IIRC part of the nauty package). The last two are optional packages in sage, so probably installing sage (possibly in a virtual machine) is the easiest way.


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.