8
$\begingroup$

I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if they are isomorphic.

In particular, I'm looking for a simple algorithm that is easy to implement with a reasonable performance on most graphs (worst case super-polynomial, of course). I'm expecting small graphs, so performance doesn't have to be stellar, just good enough.

Unfortunately, most things I've found are highly complex and more interested in expressing deep mathematical connections than simply describing the algorithm. I'm afraid I don't have the time to dive that deep. Can anyone give me a shortcut?

I'm hoping for something like the Floyd-Warshall algorithm. Not optimal, but good enough, and easy to implement.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Are the graphs labelled consistently? If yes, just write down all the edges and sort the list. $\endgroup$ – adrianN Sep 16 '13 at 14:26
  • $\begingroup$ Ah, sorry. The vertices and edges are labeled, but not uniquely. Each label can occur mulitiple times. I guess the mathematical phrase is "coloured" rather than labeled. I'll edit the question. $\endgroup$ – Peter Sep 16 '13 at 14:49
  • $\begingroup$ "worst case NP, of course" -- just so that we are clear: there is known (deterministic) polynomial-time algorithm for graph-isomorphism, so the best you can expect is a super-polynomial solution. And yes, the problem is in NP. See here for details on these notions. $\endgroup$ – Raphael♦ Sep 17 '13 at 7:50
  • $\begingroup$ @Raphael You're right, more inexact terminology. Worst case is super-polynomial. There are average-case polynomial algorithms, though, so that should at least be achievable. $\endgroup$ – Peter Sep 17 '13 at 9:02
  • $\begingroup$ @Raphael The best you can expect is a fast algorithm that works for most graphs. $\endgroup$ – Yuval Filmus Sep 17 '13 at 16:37
3
$\begingroup$

Brendan McKay and Adolfo Piperno have written a survey paper regarding this question in 2013. They present several efficient computer programs that canonicalize many graphs faster than you would imagine. There is no need (and no point) in implementing these algorithms yourself - they are available online, even as source code.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ There is a reduction between colored GI and GI (with constant multiplicative blowup given a constant number of colors), or perhaps the algorithms themselves could be modified. $\endgroup$ – Yuval Filmus Sep 17 '13 at 16:41
  • $\begingroup$ Can you describe one here as to give a full answer? $\endgroup$ – Raphael♦ Sep 17 '13 at 19:35
  • 3
    $\begingroup$ For each color, add an extra vertex. Connect each original vertex to the vertex representing its color by adding an edge. Make sure that the degrees of the "color" vertices are unique - if this is not the case, add loops or other fake edges. By the way, I am less than happy about the McKay/Piperno survey paper - it is a survey of their own research, and the comparisons they make to other tools are on the benchmarks that they consider interesting. They omit important recent developments and almost all benchmarks derived from non-theoretical applications, which affects empirical results. $\endgroup$ – Igor Markov Sep 18 '13 at 21:51
2
$\begingroup$

I ended up implementing the Nauty algorithm, but in doing so, I did figure out an answer to my own question. Nauty extends this basic algorithm with many complicated heuristics:

Given a small graphs G of length n:

  1. Loop over all $n!$ permutations of its vertices.
  2. Generate a string representation of each (one-to-one).
  3. Define some canonical ordering of strings, and remember the smallest string encountered.

This algorithm is $O(n!)$, but for small graphs it should work fine.

Nauty extends this algorithm primarily by pruning the search space of graphs to consider, when looking for the one with the smallest string representation.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ The graphs must be really small if this brute-force approach is plausible. Even $15!$ is greater than $10^{12}$. $\endgroup$ – David Richerby Jun 13 '16 at 11:53
  • 1
    $\begingroup$ @DavidRicherby Absolutely. However, there are use cases, such as motif analysis, where this operation is only done on graphs of size 3 or 4. In fact, I don't know if finding a canonical isomorphic subgraph can be achieved in reasonable time at all for graphs over 15 nodes (even if subgraph isomorphism itself is now known to be very close to polynomial) $\endgroup$ – Peter Jun 13 '16 at 12:09

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.