Computational Combinatorics

Month: August, 2012

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 »

Computational Combinatorics Reference List

There are a lot of things I want to discuss on this blog. So many, in fact, that I struggle to pick which topic to write about next. I have compiled a list of papers and user guides that are possible topics for later blog posts. This should give you an idea of what topics I want on the blog and also some reading material if you don’t want to wait for me to get there. Also, if you want to write a guest post discussing these or similar papers (or simply want to add a paper to the list), please send me an email! I promise a regular post next week.

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 »

Example: Piping geng

I realized shortly after writing yesterday’s post about using gtools that I did not properly explain the piping procedure for geng. To remedy that deficiency, I will provide a concrete example of how I used this method in actual research.

In this example, we will exactly characterize the infinite class of p-extremal graphs for p \leq 10. We’ll start by talking about the mathematics, and at the very end we will go into the concrete piping example. Theoretically, you could skip straight to the code, but you’ll miss out on the fact that the computer is simultaneously discovering and proving a structure theorem for an infinite class of graphs!
Read the rest of this entry »

Tips and Tricks: Using gtools

If you want to get down and dirty with computational methods but don’t want to do a lot of programming, you can get started now using Brendan McKay‘s gtools software, part of the nauty library. It’s free software, but you’ll need to compile it yourself. This software allows you to generate graphs in several different ways, usually finding all graphs with certain properties up to isomorphism. The output is not human-readable, but you can use the output to create graphs in Sage or just count the number of graphs with that property. Everything I write below is available in the user manual, but read ahead for a slightly different treatment.

Read the rest of this entry »