Computational Combinatorics

Tag: canonical deletion

Generating Cubic Graphs

Today, we return to the canonical deletion method to generate cubic graphs. Cubic graphs are 3-regular graphs, and since the degree is constant, there are many fewer cubic graphs of order n than general graphs of order n. Also, since the structure of cubic graphs is very restricted, we can use custom augmentations to generate them more quickly than using an augmentation that works for general graphs.

This implementation of the method comes from Brinkmann, Goedgebeur, and McKay in their paper Generation of Cubic graphs from Discrete Mathematics and Theoretical Computer Science. By desigining custom augmentations, they are able to restrict their generation algorithm to create only connected cubic graphs. This augmenation is paired with a canonical deletion step which removes all isomorphic duplicates. Their implementation is given in the snarkhunter software, which is the current-fastest implementation to generate cubic graphs (and snarks; the generation snarks is investigated in a different paper).
Read the rest of this entry »

Small Graphs are Reconstructible

One of the most famous examples of using canonical deletion was McKay’s method to verify (for small graphs) one of the oldest open problems in graph theory: the Reconstruction Conjecture. This is a natural example to discuss the benefits of canonical deletion for two reasons:

  1. It uses vertex augmentations/deletions as in our standard examples.
  2. By slightly customizing the canonical deletion, we can significantly improve the running time over simply generating graphs and testing the conjecture on all pairs.

Read the rest of this entry »

Introduction to Canonical Deletion

Today, I discuss McKay’s isomorph-free generation technique, commonly called canonical deletion, or canonical construction path. The technique guarantees that every unlabeled object of a desired property will be visited exactly once. The word visited means that a labeled object in the isomorphism class is generated and tested for the given property and possibly used to extend to other objects. Also, objects that do not satisfy the property are visited at most once because we may be able to use pruning to avoid generating objects that do not lead to solutions.

The canonical deletion technique is so called from its use of reversing the augmentation process in order to guarantee there is exactly one path of augmentations from a base object to every unlabeled object. Essentially, a deletion function is defined that selects a part of the combinatorial object to remove, and this function is invariant up to isomorphism. Then, when augmenting an object this augmentation is compared to the canonical deletion of the resulting object to check if this is the “correct” way to build the larger object. If not, the augmentation is rejected and the larger object is not visited. By following the canonical deletion from any unlabeled object, we can reconstruct the unique sequence of augmentations that leads from a base object to that unlabeled object. Further, this process is entirely local: it depends only on the current object and current position within the search tree. This allows the process to be effective even when parallelizing across computation nodes without needing any communication between nodes, unlike some other isomorph-free generation methods which require keeping a list of previously visited objects. Along the way, we will use a consistent example of generating a certain class of graphs to make the discussion more concrete.

Read the rest of this entry »

An Incomplete List of Computational Techniques

Before I have a chance to populate this blog with detailed introductions to specific techniques, we should first investigate a short list of techniques that I plan to write about. Not only does this provide me with a list of posts to write, but provides you with some keywords to look up if you are in need of a computational method now. As I see it, there are four main types of techniques: Enumerative, Exhaustive, Existence, and Non-Existence.

Read the rest of this entry »