Backtrack Search

This post is the first of a series which will explore backtracking search in permutation groups. These articles concentrate on the theory of backtracking, rather than highly-optimised implementations.

If you have any comments or corrections on these pieces, or just enjoyed reading them, e-mail me.

This post assumes you are familiar at least permutations and permutation groups. All code examples will use the GAP language. I strongly recommend installing the latest version of GAP and following along!

Introduction

Let’s dive in and consider the problem of intersecting two permutation groups G and H. G and H will be given as a set of generators. In GAP, the Group function constructs a group given by a list of generations, and the Intersection function finds the intersection of two groups (again, as a list of generators). Let’s see a short example:

G := Group((1,2,3), (1,2), (1,4)(2,5)(3,6));
H := Group((1,3,6), (3,6), (1,2)(3,4)(5,6));
R := Intersection(G,H);
# Group([ (4,5), (1,3)(4,5), (1,4,3,5)(2,6) ])

We will use lines start # to show GAP’s output

So, how can we implement the Intersection function? You might hope the next step will be a clever mathematical trick, which finds the intersection quickly. Unfortunately at present there is no algorithm that finds all intersections quickly. This problem is wrapped up in various other important problems in computer science, such as if graph isomorphism or NP-complete problems can be solved quickly, which are aren’t going to get into here.

However, just because we can’t produce an algorithm that’s always fast, we can make our best attempt to produce something fast for as many groups as possible.

Let’s start with the simplest possible implementation of intersection: Generate all permutations in G, and check if they are in H:

IntersectionEnumerate := function(G,H)
  local result, g;
  result := [];
  for g in G do
    if g in H then
      Add(result, g);
    fi;
  od;
  return Group(result);
end;

IntersectionEnumerate(G, H);
# Group([ (), (4,5), (1,3), (1,3)(4,5), (1,4)(2,6)(3,5),
#         (1,4,3,5)(2,6), (1,5,3,4)(2,6), (1,5)(2,6)(3,4) ])

One obvious problem here: Haven’t I just changed one piece of GAP magic (Intersection) for two different pieces of GAP magic:

  • Getting all elements of a group withfor g in G1
  • Check if a permutation is in a group with if g in G2

Iterating over the members of a permutation group and checking if a given permutation is in a group can all be efficiently implemented using a base and strong generating set, also known as a stabilizer chain. In a future post we will see how to make stabilizer chains, and how to implement methods like g in G1. For now, just accept these functions can be implemented efficiently, once you have a base and strong generating set.

If your only interest is the worst-case complexity for all intersection problems, IntersectionEnumerate is surprisingly close to the state of the art! None of the algorithms we will discuss will ever beat this algorithm by very much, in a theoretical sense. However, we can (as you might hope) outperform this algorithm in many cases!

The fundamental idea behind all of our improvements revolves around backtracking search, also known as divide-and-conquer. We will take our problem and split it up into sub-problems, which will be (hopefully) easier to solve, and then stitch our answers back together to form the entire group we are looking for.

Basic Backtracking

So, how can we split the search for Intersection(G,H) up? One natural method of attack if to consider searching for subgroups and cosets contained inside the group we are interested in. Let’s try that!

A Brief Aside: Point stabilizer

The point stabilizer of an integer x in a permutation group G is the subgroup of G which fixes x. This is often denoted by G_x. How can we find this subgroup in GAP? Firstly, let us write a slow function:

StabPointEnumerate := function(G,x)
  local result, g;
  result := [];
  for g in G do
    if x^g = x then
      Add(result, g);
    fi;
  od;
  return Group(result);
end;

StabPointEnumerate(G, 1);
# Group([ (), (5,6), (4,5,6), (4,5), (4,6,5), (4,6),
#          (2,3), (2,3)(5,6), (2,3)(4,5,6), (2,3)(4,5),
#          (2,3)(4,6,5), (2,3)(4,6) ])

Of course, we don’t want to do this in practice. It turns out finding the point stabilizer is another thing we can calculate using stabilizer chains! In GAP, we do that as follows:

Stabilizer(G, 1);
# Group([ (4,6,5), (5,6), (2,3) ])

Notice how Stabilizer produces out a shorter answer than StabPointEnumerate. Both functions produce the same group, but Stabilizer produces a set of generators rather than every element of the group.

Back to Backtracking

We will split the problem of finding G \cap H into pieces, by splitting our problem up into n pieces (where n is the largest moved point of either G or H):

  • Find p \in G \cap H where 1^p = 1.
  • Find p \in G \cap H where 1^p = 2.
  • Find p \in G \cap H where 1^p = n.

Let’s first consider the first of these sets. A permutation p where 1^p=1 is in G \cap H if and only if it is contained in G_1 and H_1. Therefore we just need to find Intersection(Stabilizer(G, 1), Stabilizer(H,1)). While this is another intersection problems, it is a smaller problem, and so will (hopefully) be easier to solve. Let’s call this intersection R.

Now we are going to apply a little group theory. We know that R \subseteq G \cap H, so we can divide G \cap H into a list of cosets of R. Let’s pick a single permutation in some coset of R – for example q = (1,3)(4,5) (which we know is in G \cap H, as we found it earlier during our brute force enumeration).

As all p \in R satisfy 1^p=1, then all permutations in the coset qR will satisfy 1^p=3. In general, in each of our subproblems, we will find either:

  • A coset of R
  • No permutations

(A full proof of this is left to interested reader..)

Therefore, we don’t need to find all solutions to all of our sub-problems after the first – we only need to find one permutation from each (or prove no permutation exists)! That already gives us a significant gain in performance.

How can we find quickly which of these sub-searches contains a permutation from G \cap H? That problem has been the subject of a huge amount of research. We will discuss some methods of implementing this in coming posts.