This blog post is very similar to the post on enumerating circle graphs from a few weeks ago.

Enumerating permutation graphs

Given a permutation \(\sigma = (\sigma_1, \sigma_2, \dots, \sigma_n)\) the corresponding permutation graph is the graph with vertex set \(V = \{1, 2, \dots, n\}\) and, for \(i < j\), there is an edge \(ij\) if and only if \(\sigma_i > \sigma_j \). Much like the circle graphs that we enumerated a few weeks ago, the best list I could find is not in the most obvious format, and the OEIS entry doesn’t get that far. In fact, up until 07/09/2020 the list only went up to \(n = 10\), and you can do \(n = 11\) by simply iterating over all permutations!

There are three obvious ways of enumerating circle graphs:

1. Iterating over all permutations, computing the corresponding graphs and removing all non-isomorphic graphs.
2. Iterating over all graphs and counting how many are permutation graphs.
3. A canonical deletion approach.

1. Checking all permutations

Constructing the graph from a permutation can trivially be done by iterating over all pairs \((i,j)\) with \(i < j\) and checking if \(\sigma_i > \sigma_j\), so the first method takes only ~20 lines of code using mamba. There are only \(n!\) permutations, which is pretty good for a brute force enumeration, and this method isn’t a terrible idea. Besides, I don’t know if the number of permutation graphs is \(o(n!)\) anyway. It took only 59.7s to enumerate all the permutation graphs on 10 vertices, and 11 vertices only takes 13m 5s. That suggests that maybe 12 vertices can be done in just a few days, and maybe 13 vertices in a few weeks.

func checkAllPermutations(n int) int {
	iter := itertools.Permutations(n)

	graphs := make(map[string]struct{})
	for iter.Next() {
		v := iter.Value()
		g := graph.NewDense(n, nil)

		for i := 0; i < n; i++ {
			for j := i + 1; j < n; j++ {
				if v[i] > v[j] {
					g.AddEdge(i, j)
				}
			}
		}
		ci := graph.CanonicalIsomorph(g)
		g6 := graph.Graph6Encode(graph.InducedSubgraph(g, ci))
		graphs[g6] = struct{}{}
	}

	return len(graphs)
}

One of the reason that permutation graphs are interesting is that they are perfect graphs, and so some of the classical NP-hard problems are polynomial on permutation graphs. In general, the problem of graph isomorphism is not known to be NP-complete or to be solvable in polynomial time, but an \(O(n^3)\) algorithm for permutation graphs was found by Colbourn in 1981. While this algorithm is fast asymptotically, I don’t know how it compares to a generic algorithm in practice, and the specialised algorithm may or may not speed up this method. Since it seems unlikely that this will beat a canonical deletion approach, I’ve not tried implementing it.

2. Checking all graphs

For the second and third methods we will need a recognition algorithm for permutation graphs. The best result is an \(O(n+m)\) algorithm from McConnell and Spinrad in 2011, but we’ll stick to the simpler \(O(n^3)\) method given by Pnueli, Lempel and Even in 1971. This is a simple algorithm which exploits the fact that a graph \(G\) is a permutation graph if and only if both \(G\) and \(\overline{G}\) are transitively orientable, and it doesn’t take long to implement.

We could also make a recognition algorithm using the recognition algorithm for circle graphs we used when enumerating them. A circle graph is a permutation graph if and only if it admits an equator i.e. an additional chord which intersects all other chords. This phantom equator would be a dominating vertex and we can equivalently ask that the graph plus a dominating vertex is a circle graph. This is incredibly quick to implement, but very slow to run.

While the number of graphs is less than \(n!\) for very small values of \(n\), this breaks down at \(n = 10\) and the number of graphs which we check and reject starts to massively outnumber the permutation graphs. However, checking if a small graph is a permutation graph is quite quick and even at \(n=10\) it seems to be quicker to check all graphs than to check all permutations. But for \(n=11\), there are 169x more unlabelled graphs than unlabelled permutation graphs and this is much slower than checking all permutations.

3. Canonical Deletion

Removing any vertex from a permutation graph gives a permutation graph, so we can plug the recognition algorithm into our basic canonical deletion algorithm with no modifications! Since the complement of a permutation graph is again a permutation graph (corresponding to the reverse permutation), we could speed this up by only counting graphs with at least \(\frac{1}{2} \binom{n}{2} \) edges and then adding in their complements, and this seems to save about a third. It cuts down the time to enumerate the graphs on 10 vertices to about 4s and the graphs on 11 vertices to about 1m, which isn’t bad, but isn’t going to allow us to get much further. It’s also worth noting that the canonical deletion currently takes a vertex of minimum degree as the vertex to remove so we have to count graphs with at least \(\frac{1}{2} \binom{n}{2} \) edges and not at most. This makes it a bit fragile (it will break if we switch to removing a vertex of max degree), and the conditions used in the canonical deletion are currently undocumented/subject to change.

Results

The table below gives the time to run each of the three methods once. Some of the early \(n\) are very small and would really need to be run many times to get a more reliable estimate, so we can pretty much ignore the first half of the table. Each trial was run with a single goroutine and given one hour.

By splitting the canonical deletion across 20 goroutines and leaving the code running for a few hundred hours, we can count the number of circle graphs on 12, 13 and 14 vertices, as given in the table below. It’s worth noting that you can clearly see that running this code in parallel for \(n = 12\) added quite a bit of CPU time, but this isn’t really a fair comparison. For one, the parallel code below was outputting all the graphs and writing them to file, instead of just counting the graphs. The code was also run on a different, shared computer that, as well as potentially being slower (or faster) per core, was pinned to 100% CPU usage with many other jobs. In fact, the repeated work done by every process should only be up to \(n = 8\) which only takes 55ms, and this should only add a second or so to the overall time.

Code

• Enumerate permutation graphs