Breaking Symmetries in Graph Representation

1 Introduction

The canonical graph representation problem is pertinent to a wide range of scientific applications. It is closely related to the graph isomorphism problem, as two graphs are isomorphic if and only if they have the same canonical representation. Examples of applications include data-mining [Washio and Motoda, 2003], mathematical chemistry [Faulon, 1998] and bio-informatics [Gardiner, 2011]. The two problems are poly-time equivalent, and are among the few that are known to be in NP but not known either to be solvable in polynomial time, nor to be NP-complete.

There are a variety of software tools devoted to solving the two problems "in practice", one of which is nauty, due to McKay [1990]. Nauty is sometimes referred to as the world's fastest isomorphism testing program. It is also able to produce a canonically-labeled isomorph of a graph to assist in isomorphism testing.

This paper is about constraint problems which involve the search for a graph that satisfies certain properties. For example, consider the problem to determine if there exists an undirected graph with 31 nodes, 81 edges, and which does not contain cycles of length 4 or less. This question arises in "extremal graph theory" [Bollob´as, 1978], and its answer is unknown [Garnick et al., 1993]. The search space for problems of this type is enormous, and search may be optimized by restricting it to focus on canonical representations, or to avoid as often as possible isomorphic graphs. The general idea is to "break" symmetries in the search space. However, it is not clear how to apply this idea when searching for a graph.

Peter J. Stuckey

Dept. of Comp. Sci. and SE and NICTA Victoria Laboratory University of Melbourne, Australia

In this type of problem the graph is a variable, so graph algorithms for canonical representation and isomorphism, as well as tools such as nauty, all of which operate on given graphs, do not apply. This paper provides a solution to this problem.

We assume a setting where testing for the existence of a graph G satisfying a property P is posed as a Boolean constraint P(AG) on the variables of the Boolean adjacency matrix AG of G. We follow the approach advocated by Crawford et al. [1996], where a predicate, sb(AG), is introduced to break symmetries in the search space. In this way the satisfiability of P(AG) is equivalent to that of P(AG) ∧ sb(AG). Ideally, sb(AG) is satisfied by a single member of each equivalence class of AG under graph isomorphism, thus drastically restricting the search space for P(AG) ∧ sb(AG). However, this is not realistically possible as such a predicate also determines a canonical representation. In practice, it is sufficient that sb(AG) is satisfied by at least one member of the equivalence class of AG under isomorphism (typically by more than one) and in this case we say that sb is a symmetry breaking predicate. Shlyakhter [2007] notes that the difficulty is to identify a symmetry-breaking predicate which is both effective (rules out a large portion of the search space) and compact (so that checking the additional constraints does not slow down the search).

The presentations in [Crawford et al., 1996; Shlyakhter, 2007] consider symmetry breaking in terms of isomorphism, but focus on different structures such as acyclic digraphs, relations, permutations and functions. We introduce a novel, effective and compact predicate to break symmetries on graph representation. We consider simple graphs (undirected, with no multiple, nor self edges). We demonstrate the effectiveness of our approach through experimentation and resolve several open instances in extremal graph theory.

2 Graphs and their Canonical Representation

Throughout this paper we consider undirected simple graphs without loops or multiple edges. We focus on finite graphs and typically name the n nodes of a graph in the set {1, . . . , n}. We denote the Boolean values true and false by 1 and 0 respectively.

Definition 1 (Graph) A graph G = (V,E) has nodes V = {1, . . . , n} and edges E ⊆ V × V where (x, y) ∈ E ⇒ (y, x) ∈ E. The Boolean adjacency matrix, AG of G, is the n × n symmetric matrix where AG[x, y] ↔ (x, y) ∈ E. The ith row of matrix A is denoted by A[i], and A[i, j] denotes the j th element of A[i]. The degree of node u ∈ V is degree(u) = |{(u, v) | (u, v) ∈ E}|. We denote the minimum and maximum degrees of the nodes in G as δ(G) and ∆(G), or δ and ∆ when the context is clear.

Example 1 Figure 1 illustrates three graphs with corresponding adjacency matrices.

We use cycle notation to represent permutations. For example, the permutation (1,2,6)(3,4) maps 1 to 2, 2 to 6, 6 to 1, and 3 to 4, 4 to 3, and 5 to 5.

Definition 2 (permuting nodes) Let G = (V,E) be a graph with n nodes, AG the adjacency matrix for G, and π a permutation on 〈1, . . . , n〉. Then π(G) is the graph represented by permuting the nodes of G using π. Formally, π(G) = (V, E′ ) where E′ = {(π(x), π(y)) | (x, y) ∈ E} and π(AG) is the adjacency matrix of π(G).

Definition 3 (graph isomorphism) G and G′ are isomorphic if there exists a permutation π such that AG = Aπ(G′ ).

Example 2 The graphs in Figure 1 are isomorphic. We can permute G1 to G2 using π1 = (2, 8, 5, 9, 4, 7, 3) and G1 to G3 using π2 = (2, 9, 4, 8, 6, 7, 3).

Definition 4 (sequences, lexicographic order) Let A a be matrix and A[i]A[j] the concatenation of rows i and j (viewed as sequences). The length of a sequence s is denoted |s|. We use ⪯ to denote the usual lexicographic order on sequences. We extend this notation in the obvious way: for matrices, with n and m rows respectively, A ⪯ B, if and only if A[1]A[2] · · ·A[n] ⪯ B[1]B[2] . . .B[m]; and for graphs, G ⪯ G′ if and only if AG ⪯ AG′ .

One way to define a canonical representation of a graph is to take the smallest graph (i.e. in the lexicographic order) which is isomorphic to G [Read, 1978]. This is the definition which we adopt throughout the paper.

Definition 5 (canonical form of a graph) The canonical form of a graph G is the graph with can(G) = min⪯{π(G) | π is a permutation}. We say that G is canonical if G = can(G).

Example 3 Consider the graphs of Figure 1. The graph G3 is the canonical representation of G1, G2 and G3.

Note that the canonical representation of a graph does not necessarily order the nodes by degree. In Figure 1, the nodes of G2 are ordered by degree: nodes {1, 2, 3, 4} are of degree 2, nodes {5, 6, 7, 8} are of degree 3 and node 9 is degree 4. But this is not the case for the canonical form, G3.

3 Symmetry breaking on Representation

We first consider a symmetry breaking predicate, introduced without proof in [Miller and Prosser, 2012], which constrains the rows of the adjacency matrix to be sorted lexicographically in non-decreasing order.

Definition 6 (lexicographic symmetry break) Let A be an n × n adjacency matrix. We define

Observe the graphs in Figure 1. We have sbℓ(AG1 ) = false, sbℓ(AG2 ) = false, and sbℓ(AG3 ) = true.

Definition 6 is more subtle than might first appear. It defines a symmetry breaking predicate only because for every adjacency matrix A, sbℓ(A′ ) is true for at least one of the matrices A′ isomorphic to A. No such proof is provided in [Miller and Prosser, 2012]. In fact, were we to reverse the order, taking A[i] ⪰ A[i + 1] instead, it would not define a symmetry breaking constraint. Consider for example any representation of the graph G with 2 nodes and a single edge. Then AG[1] ̸⪰ AG[2]. The subtlety arises because, in contrast to the case of breaking symmetries in matrix problems where rows and columns can be reordered, such as in [Gent et al., 2002; Flener et al., 2002; Frisch et al., 2003], here we need to reorder rows and columns both in the same way. To prove the correctness of Definition 6 it is sufficient to show that sbℓ(can(A)) holds.

Theorem 1 Let G be a graph. Then sbℓ(can(AG)).

Proof: Let A be canonical and assume to the contrary that A does not satisfy sbℓ(A). Let i be such that A[i] ̸⪯ A[i + 1]. It follows that there is a j such that for every 1 ≤ j ′ < j, A[i, j ′ ] = A[i+1, j ′ ] and A[i, j] = 1 and A[i+1, j] = 0. Let A′ be the matrix obtained by swapping rows i, i + 1 as well as columns i, i + 1. We show that A′ ≺ A in contradiction to A being canonical. Considering that A[i, j] = 1, so i ̸= j and there are two cases. We detail the case for i < j. The other case is similar.

If i < j, note that because the j - 1 length prefixes of A[i] and A[i + 1] are equal, hence A[i, 1] · · ·A[i, j - 1] = A′ [i, 1] · · · A′ [i, j - 1]. Note also that A[i′ ] = A′ [i′ ] for i′ < i (the i and i + 1 elements in A[i′ ] are equal because A is symmetric and A[i, i′ ] = A[i + 1, i′ ]). It follows that the first cell to differ in A and A′ is A[i, j] = 1 and A′ [i, j] = 0. So A′ ≺ A. Contradiction. □

We now proceed to strengthen this notion of symmetry breaking. The following example illustrates a symmetry not captured by sbℓ(A).

Example 4 Consider the adjacency matrix A1 depicted in Figure 2 for which sbℓ(A1) = true as the rows are ordered lexicographically. Observe that A[2] ⪯ A[3] independent of whether we swap the nodes (rows and columns) 2 and 3, or not. Adjacency matrix A2 depicted in Figure 2 is the result of this swap and it too satisfies sbℓ(A2) = true. However, it is "closer" to canonical as A2 ⪯ A1. Indeed A2 is the canonical representative of this graph. Figure 2 highlights that the first 3 elements of rows 2 and 3 are invariant under node swap.

In view of Example 4 we introduce the following definition and then introduce a stronger symmetry breaking constraint.

Definition 7 (extended lexicographic order)

Let s be a sequence and I ⊆ {1, . . . , |s|}. We denote by (s ↾ I) the sequence obtained from s by simultaneously omitting the elements at positions I. For a set of natural numbers I we denote by ⪯I the order on sequences of length at least max(I) defined by: s1 ⪯I s2 ⇔ (s1 ↾ I) ⪯ (s2 ↾ I).

����

����

����

����

����

����

����

����

Definition 8 (improved lexicographic symmetry break) Let A be an n × n adjacency matrix. We define

Observe that Definition 8 introduces O(n2 ) constraints on lexicographic order whereas Definition 6 introduces only O(n). This is needed because we lack a "transitivity" like property stating that if s1 ⪯{i,j} s2 and s2 ⪯{j,k} s3 then also s1 ⪯{i,k} s3. But this does not hold as illustrated by the following example.

Example 5 Consider the adjacency matrix A shown in Figure 3. While clearly A[1] ⪯{1,2} A[2] and A[2] ⪯{2,4} A[4], it is not the case that A[1] ⪯{1,4} A[4].

Interesting, transitivity does hold for rows two apart.

Proof: Assume the premise and adopt the following representation where the boxed elements are at positions i, i + 1 and i + 2.

From the premise by definition of ⪯I, we have S1yT1 ⪯ S2zT2 and S2xT2 ⪯ S3yT3. We prove that S1xT1 ⪯ S3zT3 which gives the result. There are two cases: either (a) S1 ≺ S2, and since S2 ⪯ S3 we have S1 ≺ S3 and the result holds; or (b) if S1 = S2, then either S2 ≺ S3, and the result follows, or S2 = S3, and it remains to show that xT1 ⪯ zT3. So we have S1 = S2 = S3. Suppose y ≺ z then since x ⪯ y we have that x ≺ z and the result holds. Otherwise, y = z. Suppose x ≺ y then clearly x ≺ z and the result holds. So assume x = y = z. Then we have that T1 ⪯ T2 and T2 ⪯ T3 and hence the result holds. □

So we can refine Definition 8.

Corollary 1

The following proves that sb∗ℓ is a symmetry-breaking predicate.

Theorem 3 Let A be a canonical adjacency matrix. Then sb∗ℓ (A) holds.

Proof: Let A be the canonical adjacency matrix for a graph G and assume to the contrary that A does not satisfy sb∗ℓ (A). That is, there exist i and j such that i < j and A[i] ̸⪯{i,j} A[j]. Let π denote the permutation which swaps nodes i and j in G. We show that B = Aπ(G) ≺ A.

A[j] = T1 x T2 0 T3 such that the circled 0 and x are at positions i and j in A[i] and at positions j and i in A[j]. They are circled to correspond to Figure 4(a). Since A[i] ̸⪯{i,j} A[j], hence S = S1S2S3 ≻ T1T2T3 = T. Since S ≻ T, hence S and T must have prefixes of the form W1 and W0, respectively. Namely, W is a common prefix followed by a 1 in S and by a 0 in T. Let k be the column where this first difference occurs (so |W| = k - 1). It is not possible that k = i since this column does not occur in S and T .

Consider the case where k < i. The first k-1 rows in A and B are identical. This is clear except for columns i and j. But these are the same as rows i and j (because of symmetry) and hence identical in the first k - 1 positions. We show that B[k] ≺ A[k]. Let A[k] = V 1X0W where |V | = i - 1 and |V 1X| = j - 1, then by construction B[k] = V 0X1W and B ≺ A. The proof for the second case, k > i, is similar. □

Note that often we may wish to separate nodes of the graph into equivalence classes a priori, and generate a graph that satisfies those equivalence classes. We can still use (extended) lexicographic ordering to help constrain the resulting adjacency matrices, since we can extend Theorem 3 to this case.

Definition 9 (ordered partition)] Let G be a graph. Then P = {P1, . . . , Pp} is an ordered partition of the nodes of G if ∀1 ≤ i < j ≤ p then vi ∈ Pi ∧ vj ∈ Pj ⇒ vi < vj .

Definition 10 (partition preserving permutation) Let P = {P1, . . . , Pp} be an ordered partition on the nodes of G. A permutation π on the nodes of G is partition preserving for P if ∀1 ≤ i ≤ p, ∀vi ∈ Pi, π(vi) ∈ Pi.

Example 6 Consider the graph G2 from Figure 1 and the ordered partition P = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9}}, which partitions vertices by degree. Then the permutation π = (2, 3, 4) is partition preserving for P. It maps elements in P1 to other elements in P1 and elsewhere is the identity.

Definition 11 (canonical partitioned adjacency matrix) The canonical form of a graph G with respect to an ordered partition P is the graph can(G, P) = min⪯{π(G) | π is a partition preserving permutation for P}. We say that G is canonical for P if G = can(G, P).

We can define a symmetry breaking predicate for partitioned graphs as follows:

Definition 12 (partitioned lexicographic symmetry break) Let A be an n × n adjacency matrix and P = {P1, P2, . . . , Pp} be an ordered partition. We define

Theorem 4 Let G be a canonical partitioned graph for an ordered partition P . Then sb∗ℓ (AG, P ) holds.

Proof: Let A be the canonical adjacency matrix for graph G and assume to the contrary that A does not satisfy sb∗ℓ (A, P ). That is, there exists a partition Pk and {i, j} ⊆ Pk with i < j where A[i] ̸⪯{i,j} A[j]. We show that B = Aπ(G) ≺ A where π swaps i and j. Note that π is a partition preserving permutation for P. The remainder of the proof is essentially identical to that of Theorem 3. □

4 Extremal Graph Problems

We apply a constraint-based approach to extremal graph problems and illustrate the advantage of symmetry breaking on the graph representation.

The girth of a graph is the size of the smallest cycle contained in it. Let Fk(v) denote the set of graphs with v vertices and girth at least k +1. Let fk(v) denote the maximum number of edges in a graph in Fk(v). A graph in Fk(v) with fk(v) edges is called extremal. The number of non-isomorphic extremal graphs in Fk(v) is denoted Fk(v). Extremal graph problems are about discovering values of fk(v) and Fk(v) and about finding witnesses. In [Abajo and Di´anez, 2010] the

Figure 5: Basic constraint model for extremal graph problems (no cycles of length 4 or less)

authors attribute the discovery of values f4(v) for v ≤ 24 to [Garnick et al., 1993] and for 25 ≤ v ≤ 30 to [Garnick and Nieuwejaar, 1992]. In [Garnick et al., 1993] the authors report values of F4(v) for v ≤ 21. In [Garnick et al., 1993] and [Wang et al., 2001] the authors apply algorithms to compute lower bounds on f4(v) for 31 ≤ v ≤ 200. Some of these lower bounds are improved in [Abajo et al., 2010]. Values of f4(v) for v ≤ 30, and of F4(v) for v ≤ 21 are available as sequences A006856 and A159847 of the On-Line Encyclopedia of Integer Sequences [OEIS, 2010].

Our basic constraint model is depicted as Figure 5 where we assume that A is a Boolean v × v matrix. Constraint (1) states that the graph is simple (symmetric with no self loops), Constraints (2) and (3) express that there are no cycles of length 3 and 4, and Constraint (4), that the number of edges is e. Constraints (2) and (3) are implemented more efficiently. We introduce additional Boolean variables for each triplet of (distinct) vertices i, j, k with i < k: xi,j,k ↔ A[i, j] ∧A[j, k] represents a length 2 path between i and k via j; and xi,k ↔ ∨{xi,j,k | j ̸= i, j ̸= k} represents the existence of any length 2 path between i and k. We then express Constraints (2) and (3) as ∀i,k. A[i, k] + xi,k < 2 and ∀i,k. ∑j xi,j,k < 2.

To explain Constraint (5) we recall Propositions 2.6 and 2.7 from [Garnick et al., 1993] which state that for every graph in F4(v) with e edges the minimum and maximum vertex degrees, denoted δ and ∆, satisfy the following equations (assuming v ≥ 1):

Given values for v and e we model the problem separately for each potential pair (δ,∆) introducing Constraint (5). In addition to the above constraints we introduce symmetry breaking constraints sbℓ or sb∗ℓ .

Example 7 For v = 31 and e = 80 the possible (δ,∆) pairs satisfying Equation (⋆) are {(4, 6), (4, 7), (5, 6)}. Similarly, for v = 31 and e = 81 the single pair is (5, 6).

We describe three experiments to evaluate the impact of different symmetry breaking strategies. Experiments were run using two different constraint solvers, BEE [Metodi and Codish, 2012] and Choco [Laburthe and Jussien, 2004]. We present the results obtained using BEE which compiles finite domain constraints to CNF and solves them using an underlying SAT solver. Our configuration uses CryptoMiniSat v2.5.1 [Soos, 2010]. BEE performs CNF simplification by applying a constraint-driven technique called equipropagation [Metodi et al., 2011] and partial evaluation. All experiments are performed on a single core of an Intel(R) Core(TM) i5-2400 3.10GHz CPU with 4GB memory under Linux (Ubuntu lucid, kernel 2.6.32-24-generic). BEE is written in Prolog and run using SWI Prolog v6.0.2 64-bits. All experiments were replicated and verified using the Choco constraint programming toolkit.

4.1 Experiment 1: computing f4(v)

Table 1 summarizes the results for a constraint-based approach to compute values of f4(v). We compare the computation time for three configurations specified as columns for: no symmetry, and breaking symmetries using sbℓ and sb∗ℓ .

For smaller instances, v ≤ 15, we apply the constraint model from Figure 5. For larger instances, 16 ≤ v ≤ 24, we add an additional constraint to the model. To this end we follow [Garnick et al., 1993] where it is noted that every graph in F(v) with at least 5 vertices contains a (∆, δ - 1)-star. In general, an (m, n)-star is a rooted tree, denoted Sm,n, with m children, each of which has n ≥ 1 children, all of which are leaves. So, we add constraints to explicitly embed S∆,δ-1 in the adjacency matrix. In this setting, based on Theorem 4 we impose symmetry breaking on the m clusters of n leaves of Sm,n as well as to the cluster of nodes not in Sm,n. Figure 6(a) illustrates the star S6,4. A 31 × 31 adjacency matrix with an embedded S6,4 is depicted as Figure 6(b). Black and white cells indicate values 1 and 0 respectively, and gray cells indicate unassigned Boolean variables. The last row of the matrix corresponds to the root. Then moving up we find the 6 children of the root, and then its 24 grandchildren. We will later return to explain Figure 6(c). Finally, in the third part of the table, we consider two open instances. Here we also consider a model with the constraints that embed the star.

For each value of v and each type of symmetry break, we search for a graph with f4(v) edges (columns e= f4(v)), and show the non-existence of a graph with f4(v) + 1 edges (columns e= f4(v)+1). Examining the three e= f4(v) columns, it appears that there is no significant gain in symmetry breaking when the instance is satisfiable and we need only find a single witness. When instances are unsatisfiable (the three e = f4(v)+1 columns) we encounter two types of instances: those which involve search and those which do not. For the later type, unsatisfiability derives from the propagation of the constraints in Equation (⋆) and the computation is fast for all three configurations. For the other instances, the solver must explore the entire search space and symmetry breaking is then useful.

The bottom two rows in Table 1 describe our results for two open instances, computing f4(31) and f4(32). A lower bound of f4(31) ≥ 80 is given in [Garnick et al., 1993] and a witness (discovered using our model in less than 2 seconds) is depicted as Figure 6(c). It is canonical with respect to a partitioning where the first 24 rows form 6 clusters of size 4 each (the grandchildren), the next 6 rows form a cluster (the children), and the last row is a singleton cluster (the root). With the proof that there is no witness with 81 edges (determined using our model in 40 minutes of CPU time) we conclude that f4(31) = 80. Given that f4(31) = 80, Equation (⋆) implies that f4(32) ≤ 85 and hence that the lower bound f4(32) ≥ 85 reported in [Garnick et al., 1993] is the precise value, consequently f4(32) = 85. These are both new results.

4.2 Experiment 2: computing F4(v)

In this experiment we apply a constraint-based approach to compute the number of non-isomorphic extremal graphs with v vertices. We apply a constraint solver to generate all graphs satisfying the constraint model for v vertices and e = f4(v) edges with corresponding symmetry breaking constraints. We then apply nauty to determine the number of non-isomorphic graphs within this set. The time required to run nauty is negligible and not detailed in our results.

For smaller values, v ≤ 15, we consider the constraint model of Figure 5. Table 2 shows for each value of v the maximum number of edges f4(v), the number of non-isomorphs F4(v), and the number of graphs generated (columns sols) and computation time (time), for each of the three configurations. Our results are as expected: improving symmetry breaking makes a significant difference. The bottom two rows in Table 2 describe our results for two open instances, computing F4(24) and F4(32). To obtain these results we first extend, in the following lemma, the observation of Garnik regarding the embedding of a star for the two cases. We then explicitly embed the extended structures in the encoding.

Proposition 1 (a) Every extremal graph G with 24 nodes contains a star S5,3 in which the 5 children of the root have degrees 5, 5, 5, 4, 4 in G. (b) Every extremal graph G with 32 nodes contains a star S6,4 in which the 6 children of the root have degrees 6, 5, 5, 5, 5, 5 in G.

4.3 Experiment 3: computing f5(v)

For our final experiment we consider the extremal graphs which contain no cycles of length 5 or less. To this end we extend the basic constraint model of Figure 5 with an additional constraint that states that every sequence of five vertices does not form a cycle, and we consider the optimization problem which computes values of f5(v). Table 3 shows our results. To better illustrate the impact of improved lexicographic symmetry breaking we consider also a predicate sb+ℓ which is like sb∗ℓ but only compares consecutive rows of the matrix. It is clear that the much larger sb∗ℓ pays off, reducing computation time considerably for the larger instances.

5 Conclusion

Symmetry breaking for graph representations using sbℓ is considered also in [Miller and Prosser, 2012] where it is shown to have a considerable impact. However, no formal justification is provided. We address in general terms the application of symmetry breaking to improve the search for an undirected graph satisfying a given property. We formally justify the use of sbℓ. We also introduce and formally justify the use of sb∗ℓ which is a more powerful symmetry breaking predicate. We demonstrate the impact of symmetry breaking to extremal graph theory where we also close several open instances.