In Orderly algorithms for generating restricted classes of graphs, Colbourn and Read expand on the earlier introduction of the orderly generation of graphs.

Briefly, orderly generation allows you to exhaustively generate all non-isomorphic graphs on p vertices, by augmenting the canonical set of (p, q) graphs (with q edges) with all possible new edges: leading to a new set of (p, q + 1) graphs. Each generated graph must be checked to ensure it is canonical before it is added to the (p, q + 1) list.

Colbourn and Read state:

The importance of the orderly methods is that, unlike classical
methods, they do not search through the graphs already in (p, q + 1) to
determine if the graph being produced is a duplicate.

What I'm confused about is that their method already requires an "is canonical?" check. If that check is as difficult as simply creating the canonical labeling of the graph, then it seems the method doesn't provide much advantage, since you could simply generate the canonical representation of the graph and determine if it has already been generated (e.g., via a simple dictionary lookup).

So it seems that this approach saves computation in the case that the cost to check "Is this graph canonical?" is of a smaller order than "Compute the canonical form of this graph." Is that the case in general? For restricted cases of graphs?

Even if that were not the case, the approach is still useful since it doesn't require the dictionary lookup in a potentially large set of generated graphs, but that seems much less interesting that if it actually resulted in a cheaper (order-wise) generation of graphs.

  • 1
    $\begingroup$ Checking whether a graph is canonical is (potentially) easier than computing a canonical form, since you can check whether a graph is canonical by computing its canonical form and comparing the two. $\endgroup$ – Yuval Filmus Jul 13 '16 at 22:36
  • 1
    $\begingroup$ Exactly, I omitted that obvious detail above: it is clear that the is canonical? check is no harder than graph canonization - but it is not at all clear that it is easier, in general, or in specific cases. So your (potentially) is what I'm asking about. $\endgroup$ – BeeOnRope Jul 13 '16 at 22:39
  • 1
    $\begingroup$ What's the best algorithm you've found for computing the canonical form of a graph? What's the best algorithm you've found for checking whether a graph is already in canonical form? $\endgroup$ – D.W. Jul 13 '16 at 23:37

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.