2
$\begingroup$

What algorithms are known for the graph isomorphism problem? Can those algorithms be related to algorithms for other graph theoretical problems (e.g. subgraph problem, counting graph isomorphisms)?

$\endgroup$
  • 3
    $\begingroup$ Your question seems too broad. BTW the fastest known algorithm runs in $e^{O(\sqrt(n \log n))}$ (Babai et al, 1983); there are a bunch of well known softwares for GI that use some (advanced) techniques to prune the search tree: nauty, saucy, bliss, traces, conauto. For an up-to-date comparison/bibliography see Practical graph isomorphism, II. $\endgroup$ – Marzio De Biasi Dec 12 '14 at 16:21
  • 1
    $\begingroup$ I think the question is fine, and would be very interested to see a survey answer along the lines of this one: cstheory.stackexchange.com/questions/9241/… McKay's survey seems more focused on implementation issues, and less on algorithms per say. $\endgroup$ – Huck Bennett Dec 12 '14 at 18:31
  • 1
    $\begingroup$ While there are lots of algorithms for special cases of GI (planar, trees, bounded genus, bounded eigenvalue multiplicity, other graph classes), it's not like there are a whole bunch of algorithms for the general case (unlike, say, matching). Marzio De Biasi's comment pretty much sums it up... $\endgroup$ – Joshua Grochow Dec 13 '14 at 4:25
  • 1
    $\begingroup$ What research have you done? We expect you to do a significant amount of research/investigation on your own before asking, and show your research in the question. You're asking for a lot -- a comprehensive of all graph isomorphism algorithms is probably too much to ask others to provide -- so you should demonstrate a comparable amount of effort on your own first, before asking. $\endgroup$ – D.W. Dec 13 '14 at 6:58