Computational Combinatorics

Tag: enumerative methods

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 »