Finding Cliques and Independent Sets in Circulant Graphs
by Derrick Stolee
We recently discussed cliquer, a “fast” algorithm for finding and counting maximum cliques in a graph. Today, I would like to discuss a modification of this algorithm when applied to graphs that have a very restrictive form of symmetry. Specifically, we will discuss circulant graphs and interval subgraphs of distance graphs. These graphs are particularly important for discovering the independence ratio of distance graphs, as discussed in the recently submitted paper, On the independence ratio of distance graphs with James Carraher, David Galvin, Stephen Hartke, and Jamie Radcliffe.
All code and data discussed is available at the distance graph page.
Let be a set of positive integers. For now, we will assume that is finite. The distance graph is the graph whose vertices are the integers, and two integers are adjacent if and only if . For an integer , the circulant graph is the graph whose vertices are the residue classes modulo and two classes are adjacent if and only if for some pair of representatives of the two classes. This is really not that complicated: Line up vertices, and for every distance , add “chords” between every pair of vertices that are positions apart.
Observe that the distance graph can be considered to be the limit object of as goes to infinity.
We consider an independent set in that is as dense as possible. That is, we define and try to maximize .
If we take an independent set in a circulant graph and let be the set of integers that are equivalent to an element of modulo , then is an independent set in . Further, it is periodic with period at most ! One of the main results in the paper is the following.
Theorem (Carraher, Galvin, Hartke, Radcliffe, Stolee). Let be a finite set of integers and . There exists a periodic set that is independent in of maximum density and the minimum period of is at most .
Thus, periodic sets achieve the optimal value, called the independence ratio . Our goal is to discover this value algorithmically using finite computations. Thus, is a lower bound on for all and these can be computed. However, unless we extend to where , then we cannot be sure our best such is also an upper bound! Thus, we also consider the graph , which is the subgraph of the distance graph that is induced by the integers . To find an upper bound on the density over the whole line, that density cannot exceed what we can fit in the interval of length ! Thus, we have the following bounds:
Thus, we want to compute and . Luckily, finding large independent sets is equivalent to finding large cliques in the complement. We will use the ideas of
cliquer in order to solve this problem!
The Algorithm for Intervals
A quick notational note: We use and .
We begin by considering the values . Observe that for all , we have . In fact, for all , we have that . We will use both facts to our advantage, where the standard
cliquer algorithm can only use the first.
For each , let , where . We shall determine each in order, using previous calculations to help. Observe that , so we will attempt to build an independent set using the element that has size at least . If we succeed, then we terminate immediately. If all attempts fail, then we know that .
Start by setting and . When an element is added to , then is removed from . Thus, we first add to and remove and from .
The recursive algorithm takes the sets , , and selects . The algorithm attempts the two choices: place in or leave out of . This is done by removing from in either case, and placing in only for the first. This will enumerate all possible independent sets in .
However, a branching algorithm is only as effective as its pruning method! We have a few ways to detect if a search node contains no possible solution. Recall that .
- If , then no extension of using elements in will create an independent set of size .
- Let be pairs such that . Then if , then no extension of using elements in will create an independent set of size .
The first prune above is the pruning mechanism directly from
cliquer. It is the second prune that is special to this restriction to . If the generators from are sufficiently “spread out,” then the set will become split into several intervals, creating small subgraphs that are used to select the rest of the independent set. While there may be edges between these intervals, perhaps most of the difficulties in creating a new independent set come from within these intervals.
These two pruning mechanisms are incomparable: there exist situations where one works and the other does not. However, the two together work to very quickly determine the clique number of intervals containing even 200 elements.
In this way, we can compute for each one at a time until we are satisfied. As we go, we can track the minimum value of for all . We cannot be sure we have computed the exact value of until we have a corresponding lower bound, which requires considering the circulant setting.
The Algorithm for Circulants
The main way that circulant graphs differ from the intervals is the “wrap around” effect. The intervals simply do not have the same difficulties with the edges, and thus are simpler to handle. Further complicating the issue is that we do not know which value will present the best lower bound of . Thus, we need to try each as we go.
For , let : the independence number of the first points in the circulant graph . Note that always, and we still have that . Thus, for each , we can compute all values for and report .
We use the same recursive algorithm as in the interval case, except we are careful of the wrap-around effect when removing elements from . Also, we use both pruning mechanisms, except the first uses and the second uses . Thus, it is important to compute the interval numbers before computing the circulant numbers.
By the previous algorithms, we can compute both lower and upper bounds on . However, since computing $latexalpha(G(n,S))$ requires instances of the algorithm with no help from , it is somewhat slower to compute each of the circulant graph ratios than to compute the interval ratios. Further, we found that the minimum such that is quite a bit lower than the minimum value such that .
Thus, we followed the pattern of computing for all before computing . Continuing until our best lower bound matches our best upper bound, we determined .
The strength of this algorithm came from the fact that there is a single automorphism such that there is a single -orbit of vertices. In fact, a graph with such an automorphism is in fact circulant, as you can relabel the vertices as for some vertex .
The concepts used by this algorithm could be extended to graphs with high-order symmetries. By selecting an automorphism that has large orbits, few orbits, or one large orbit, then perhaps there could be some improvements over
cliquer over these classes of highly-symmetric graphs.
However, (and this is a big “however”) finding such a “large” automorphism may be incredibly hard. While
nauty can find a set of generating automorphisms, I could not find many algorithms for finding automorphsims with certain properties. The best I could find is Linear optimization over permutation groups, which essentially uses branch-and-bound for a related problem. I would be very interested to see more work on optimizing more orbit-type properties of a single automorphism in the automorphism group.
C. Buchheim, M. Jünger, Linear optimization over permutation groups, Discrete Optimization 2 (2005) 308-319.
Sampo Niskanen and Patric R.J. Östergård, Cliquer User’s Guide.
Patric R. J. Östergård, A fast algorithm for the maximum clique problem, Discrete Applied Mathematics 120 (2002) 197-207.