next up previous
Next: A graph generator Up: Algorithms for Group Actions Previous: Introduction

Basic Principles

We start with some basic principles and then show how they are used in generating graphs up to isomorphism. Generally the problem of generating objects up to isomorphism can be interpreted as the problem of finding orbit representatives for a group action. Since algorithms usually also need the stabilizers of the chosen representatives, we understand by a solution of the orbit representative problem, a determination of a set of representatives together with their stabilizers.

Our approach allows us to give a solution to the generating problem that differs from that of the conventional approaches. Mathematically, one can determine the number of orbits by some variant of the Cauchy-Frobenius Lemma,see [K], which is non-constructive. This is an elegant way to get the size of the solution set. Already this method has been criticized because of its exponentional complexity. We point out however, that, as early as 1982, H. S. Wilf [Wi] gave a discussion of that problem that apparently was not recognized by complexity theory. Wilf considers the quotient of the time complexity of counting, by the time complexity of listing representatives. A counting formula is effective if this quotient tends to 0 with increasing size of the counted structures. If one is only interested in the number of orbits, his analysis shows that the Cauchy-Frobenius Lemma gives an effective solution. Since practical applications really need the solutions themselves and not just the number of solutions, there has been much effort to list orbit representatives completely. Of course, such an approach cannot lead very far when there is an exponential growth of the number of orbits. This is a motivation to generate representatives from the orbits uniformly at random.

In mathematics one can find other solutions to problems of this kind. For example, the Hauptsatz for finite abelian groups describes all finite abelian groups up to isomorphism without giving their number or listing them. Instead, there is an implicit description by lists of invariants. Though it seems intractable to find such a Hauptsatz for our problem, we make a step in that direction. So instead of listing representatives in any case, we mix listing with an implicit handling of large sections of orbits. If there is no non-trivial group action, all the objects belong to different orbits. Thus, knowing an algorithm which computes the size of the set of objects and which allows the construction of each object on demand will suffice. We say that a set O of orbits is determined if we have a rank function at hand, ranking the set O, and allowing the computation of a representative for the i-th orbit for any given rank number i. In terms of [SW] we thus require an unrank function.

To avoid a misunderstanding, we point out that we do not demand the corresponding rank function, which, given any element from any orbit, would give the rank of the orbit. Such a function would solve the general isomorphism problem for graphs, whereas finding an unrank function would be an easier problem.

We represent simple graphs as subsets of the set of all 2-element subsets of a vertex set V. Two such simple graphs are isomorphic iff they lie in the same orbit of tex2html_wrap_inline217 Thus, we have to consider induced group actions. In such situations, there is often enough structure to apply algebraic decomposition techniques. The basis of this approach is to make algorithmic use of homomorphisms.

definition222

If two group actions tex2html_wrap_inline251 are isomorphic with an isomorphism tex2html_wrap_inline253 then tex2html_wrap_inline253 carries orbit representatives and their stabilizers onto corresponding representatives and stabilizers. Thus, if isomorphisms of group actions can be found, whole sets of solutions of the orbit problem can be used many times. This allows the description of large sets of solutions implicitly in our generator, as described above.

We fix some notation we use which is partially standard. We extend the group theory notions of a normalizer and a centralizer, to the case of actions on sets of more general objects. Thus, if tex2html_wrap_inline257 is a group action and tex2html_wrap_inline259 then for each tex2html_wrap_inline261 let tex2html_wrap_inline263 and

displaymath265

the normalizer of tex2html_wrap_inline267 in G. Similarly,

displaymath271

is the centralizer of tex2html_wrap_inline267 in G. By abuse of notation, for a single point tex2html_wrap_inline277 we denote by tex2html_wrap_inline279 the stabilizer of tex2html_wrap_inline281

Suppose an epimorphism tex2html_wrap_inline283 is given. Then we may use tex2html_wrap_inline253 in two ways. Firstly, if a solution of the orbit problem is known in tex2html_wrap_inline287 then we only have to look at the preimage sets tex2html_wrap_inline289 for representatives tex2html_wrap_inline291 and let the full preimage groups tex2html_wrap_inline293 act on these sets respectively. We call this usage of tex2html_wrap_inline253 a split.

Secondly, if a solution of the orbit problem is known in tex2html_wrap_inline297 then we may use the homomorphic images of the representatives and their stabilizers to find a solution in the image domain. There is some complication, since different orbits in the preimage set may be mapped onto the same orbit. So if the image tex2html_wrap_inline299 of one representative tex2html_wrap_inline301 is used, one has to avoid the other image representatives for the elements of tex2html_wrap_inline303 It should be noted that those points tex2html_wrap_inline305 in tex2html_wrap_inline267 that are mapped onto tex2html_wrap_inline301 by some tex2html_wrap_inline311 correspond bijectively to the cosets of tex2html_wrap_inline313 in the full preimage group of tex2html_wrap_inline315 The elements tex2html_wrap_inline317 are just a set of coset representatives. Thus, one can also obtain the stabilizer of tex2html_wrap_inline291 in this way. We call this usage of tex2html_wrap_inline253 a fusion.

To point out the importance of these two interpretations, we briefly mention a typical application in construction problems. Suppose a set of representatives for the isomorphism types of a certain class of graphs is given. Then an extension step adds new subgraphs into each of these graphs. This step can be broken into two parts by the homomorphism principle. In the first part the new subgraph is added as a colored object in all possible ways up to equivalence under the automorphism group of the old graph. This is the split part of the extension. It is related to the simplification which forgets the new added subgraph. In the next half of the extension step we forget the special coloring of the subgraph. This is a simplification tex2html_wrap_inline253 where we use fusion.

For another simple example using some aspects of homomorphisms, consider the generation of multigraphs. A multigraph may be obtained by gradually increasing the highest edge multiplicity by 1. In each step only the automorphism group of the chosen representative needs to be considered with its action on the set of mappings from the set of all edges of maximal degree m to the set tex2html_wrap_inline327 This is of course a first application of a split. The percentage of simple graphs with non-trivial automorphism group tends to 0 with increasing number of vertices, [O]. Thus, in most cases we don't have any group action at all in these steps ( a recent implementation [Bg] demonstrates that already for a small number of vertices the automorphism groups of the multigraphs tend to become trivial very soon). This observation is trivial, but it is practically important, since in all these cases we can switch over to implicit handling instead of listing. Moreover, when graphs with trivial automorphism group combine to a bigger graph, these implicit listings may be combined yielding an implicit handling for a combinatorially exploding problem.

Nevertheless, the cases with non-trivial group action have to be considered. We demonstrate the use of homomorphism here with a simple example. Suppose a multigraph G has k edges of highest multiplicity m forming the edge set tex2html_wrap_inline335 Then Aut G acts on the set of mappings from tex2html_wrap_inline339 to tex2html_wrap_inline327 The orbits correspond to the multigraphs with highest multiplicity m + 1 which can be deduced from G. To solve this orbit problem we may map tex2html_wrap_inline339 onto tex2html_wrap_inline349 , tex2html_wrap_inline351 onto tex2html_wrap_inline353 and Aut G onto some corresponding subgroup U of tex2html_wrap_inline359 This is an isomorphism of group actions which maps onto an orbit problem which is independent of k. If we solve these orbit problems as in the case of simple graphs once and for all, we only have to note the isomorphism instead of all solutions. In particular, after a finite number of steps, no new orbit problems have to be solved for an unbounded edge multiplicity.

One can break up this orbit problem even further by reducing the action of U from tex2html_wrap_inline365 to tex2html_wrap_inline367 where B is an orbit of U on tex2html_wrap_inline373 This may be repeated until the stabilizer of a representative mapping is trivial or the mappings are fully determined.

As usual in algebra, simplifications by homomorphisms stop at some stage when no more non-trivial homomorphisms exist. These situations are called irreducible cases. For such cases we need another tool, i.e. orderly generation[R],[F]. We now suppose that a group G acts on a finite set X. We impose on X an ordering < such that also the set tex2html_wrap_inline383 of all subsets of X is lexicographically ordered. This ordering will not be compatible with the action of G, in general. It is therefore quite astonishing that such an ordering can be used to solve orbit problems. Each orbit tex2html_wrap_inline389 for some tex2html_wrap_inline391 contains a lexicographically minimal element tex2html_wrap_inline393 which we denote as the canonical representative with respect to <. In short we say tex2html_wrap_inline397 iff tex2html_wrap_inline399 Then we have the following fundamental lemma[HKLMW].

lemma53

Thus, we only have to enlarge representatives T of smaller cardinality by elements x which are larger than each element in T, to obtain candidates for representatives of greater cardinality. This approach can be refined noting elements y larger than each element in T which cannot enlarge T.

lemma56

The candidates obtained after removing the cases of the preceding lemma are often called semicanonical in the special case of graph generation [KP], [Gd], [Mo].

A test for minimality for each remaining candidate S, now has to decide whether there exists some tex2html_wrap_inline261 such that tex2html_wrap_inline449 The obvious strategy is to run through all tex2html_wrap_inline261 until either tex2html_wrap_inline453 or all elements of G have been tested. Of course, there must be chosen some ordering in which the elements of G have to be considered. We take a Sims chain, also called a strong generating set, with respect to the set X ordered ascendingly, as a base tex2html_wrap_inline461 This chain consists of transversals of the left cosets of tex2html_wrap_inline463 in tex2html_wrap_inline465 for tex2html_wrap_inline467 We order these representatives r by tex2html_wrap_inline471 Then we can run through all cosets tex2html_wrap_inline473 under this order of r's and, for fixed r, in ascending order through tex2html_wrap_inline479 for tex2html_wrap_inline467 There is a case where some elements of G need not be considered in this procedure [Gd].

lemma68

Thus, for a subgroup U which has already been tested, the whole left coset gU can be omitted if tex2html_wrap_inline503 is detected. Sometimes the elements of X play a different role in a bigger context. Then one has the additional condition that each tex2html_wrap_inline507 has to belong to a certain class of elements of X, tending to further restrictions for the choice of group elements. This is used in the graph generation algorithms of [McKb] and [Go], where only additions of vertices of maximal degree are considered.

Often the required solutions have to fulfill some constraints such as forbidding certain substructures. Then a check whether these constraints are fulfilled is usually much faster than a canonicity check and should be done first. It even pays to neglect the canonicity test in several consecutive extension steps, and to only check the constraints there. Then a canonicity check may reveal at a later point, that a candidate S is not minimal in its orbit, In the light of lemma 2.4 above, it is useful in such a case to determine the first extension step where this non-canonicity could have been detected. Then all further extensions of this earlier candidate must also be rejected. Depending on the selectivity of the additional constraints. a delicate balance between steps with constraint checking only, and steps with canonicity check combined with tracing back to the earliest detection point, is needed for the fastest strategy. This has been followed by MOLGEN [GKLM].

Several different strategies for solving the isomer generation problem had been pursued in different stages of the MOLGEN project. The first versions followed the DENDRAL strategy [LBFL]. There, in a finite number of steps, the isomers are constructed out of cyclic graphs. The present version uses orderly generation in filling classes of rows of the adjacency matrix [Gd] which are known to be invariant with respect to isomorphisms. For a future version we have implemented a proposal from [GKL] as a preliminary step. This generator is presently only available for simple graphs[Gr]. The generation strategy of this version makes sophisticated use of homomorphisms, and combines them with the orderly generation approach as discussed above in the irreducible cases. This new strategy is explained in the next section.


next up previous
Next: A graph generator Up: Algorithms for Group Actions Previous: Introduction