An Incomplete List of Computational Techniques

by Derrick Stolee

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.

Before we begin, I should warn you that my default mode of thinking is “Do certain combinatorial objects exist?” and not “Is this combinatorial statement true?” The reason is that usually a combinatorial statement can usually be interpreted as “All combinatorial objects with Property A also have Property B.” If you wish to verify such a statement, you can try to search for objects with Property A but not Property B. If you can determine that there do not exist objects with Property A and not Property B, then you are making progress! If you can prove that objects with Property A but not Property B have a certain size, and by using the computer we can show there are no such examples, then the theorem is proven!

Not all theorems can be tackled in this way, so sometimes we only look for evidence for or against conjectures. These techniques will almost always give you some evidence, even if it is not definitive.

Enumerative. These techniques will tell you how many objects there are of a given type. For example: How many connected, triangle-free cubic graphs are there of order 10? (Answer: there are 6. If you have nauty, run “geng 10 -d3D3ct -u”) Are all uniquely K_r-saturated graphs of order n isomorphic to a book? Which H-free graphs have the most number of edges? In this final example, we are asking an extremal question. If we can enumerate all of the H-free graphs, then we can determine which H-free graphs have the most edges.

The biggest problem with enumerative techniques is that there are either a lot of objects with a given property, or there may be none. In either case, we usually attempt to build the objects piece-by-piece using small augmentations, such as adding a vertex to a graph until reaching n vertices. Unless you can exploit the properties of your goal objects, there are a lot of graphs that will be built along the way. Further, many graphs can be built in different ways, since a computer stores a labeled version of a graph but we (generally) care about unlabeled objects. Therefore, most techniques also deal with the issue of reducing or eliminating isomorphic duplicates (or isomorphs). A few of these techniques are:

  • Canonical Deletion (or Canonical Construction Path)
  • Orbital Branching
  • Symmetry Breaking

Exhaustive. These techniques will tell you whether or not there exists an object of a given type, but will not necessarily say how many there are. Usually, the limitation of finding only one solution is due to using some software as a black box. The main example of this approach is Integer Programming, where a solver will only output a single optimal solution (yes, some solvers allow you to enumerate solutions but this is not recommened). If you want to count objects, you can implement your own solver.

Existence. These techniques may output objects when they exist, but failure to output an object does not imply that no object exists. Sometimes, this family is called Local SearchThe idea is to start with random data and modify it in some way to “approach” an object you are looking for. One example from mathematics is Erdős’ deletion method for finding a graph with arbitrary high girth and chromatic number: Take the random graph G_{n,p} (for an appropriate value of p) which will almost always have very high chromatic number and delete a small number of edges so no cycles exist. In this proof, there is almost always a small set of edges to delete. This “random sampling then modifying” approach takes several forms, as in the following techniques:

Non-Existence. These techniques may output proofs (or “certificates”) that objects do not exist, but failure to output a proof does not imply that objects exist. One such general technique is to use Nullstellensatz Certificates, (yes, as in Hilbert’s Nullstellensatz). I know of a few other examples but have no good name for them.

In the next few months, I will be writing about these techniques and providing examples of how they have been used in recent research.

Advertisements