Structural Symmetry Breaking

1 Introduction

During the past five years, symmetry breaking has been a topic of increasing interest in the constraint programming community. It was shown that symmetry breaking can play a decisive role in the solution of numerous constraint problems, and sophisticated symmetry breaking methods have been developed, such as the addition of symmetry breaking constraints (see for example [Crawford et al., 1996]), symmetry breaking by adapting the search strategy [Brown et al., 1988], symmetry breaking during search (SBDS) [Gent and Smith, 2000], or symmetry breaking by dominance detection (SBDD) [Fahle et al., 2001; Focacci and Milano, 2001]. Especially the latter has attracted a lot of interest: improvements were suggested in [Barnier and Brisset, 2002; Puget, 2002] for example. SBDD works by checking whether the current choice point under investigation represents a symmetric variant of a part of the search space that has been investigated completely before.

The core of an SBDD symmetry breaking code is dominance detection which was automated in [Gent et al., 2003] by using the generic computational group theory tool, yielding a method named GAP-SBDD. While using a generic tool is appealing from the perspective of the ease-of-use for the constraint programmer, the generality comes with no guarantee of efficiency. Therefore, in [Van Hentenryck et al., 2003], the special case of dominance detection in the presence of some classes of pure value symmetry was investigated and proven to be computationally tractable. The approach taken was generalized in [Roney-Dougal et al., 2004], where the notion of symmetry-free search trees, so-called GE-trees, was introduced. In combination with GAP, GE-trees were shown to break arbitrary value symmetries in polynomial time.

In this paper, we continue this successful line of research by studying combinations of value and variable symmetry in constraint satisfaction problems (CSPs) and CSPs with set variables (set-CSPs). We offer three main contributions: The first regards a combination of variable and value symmetry for CSPs with single-valued variables. For the first time, in Section 3, we show that the corresponding dominance detection problem is computationally tractable. In Section 4, we build up on this result and show an efficient way of using the dominance detection algorithm for filtering rather than just pruning. The third main contribution regards set variables: in Section 5 we show that the general dominance detection problem becomes NP-hard for set-CSPs that contain symmetric set variables and value symmetry. Finally, as a minor sidenote, in Section 6 we show that higher forms of symmetry where sets of set variables are symmetric to other sets of set variables in combination with value symmetry can be reduced to the partial set variable symmetry case.

2 Preliminaries

Let us start out by introducing some notation that we will use throughout the paper. In the reminder of this paper, let us assume that n, m, p ∈ IN.

Definition 1

• A Constraint Satisfaction Problem (CSP) is a tuple (Z, V,D,C) where Z = {X1, . . . ,Xn} is a finite set of variables, V = {v1, . . . , vm} is a set of values, D = {D1, . . . , Dn} is a set of finite domains where each Di ∈ D is the set of possible instantiations to variable Xi, and C = {c1, . . . , cp} is a finite set of constraints where each ci ∈ C is defined on a subset of the variables in Z and specifying their valid combinations. We say that the CSP has single-valued variables iff for all Di ∈ D it holds that Di ⊆ V . If for all Di ∈ D it holds that Di ⊆ 2 V (where 2 V denotes the set of all subsets of V ), we say that the CSP is a set-CSP.
• Given a CSP with single-valued variables, an assignment A is a set of pairs (X, v) ∈ Z × V such that (X, v), (X,w) ∈ A implies v = w. Given a set-CSP, a set-assignment A is a set of pairs (X, S) ∈ Z × 2 V such that (X, S1), (X, S2) ∈ A implies S1 = S2.

Definition 2

• Given a set S and a set of sets P = {P1, . . . , Pr} such that ⋃ i Pi = S and the Pi are pairwise non-overlapping, we say that P is a partition of S, and we write S = ∑i Pi.
• Given a set S and a partition S = ∑i Pi, a bijection π : S ↦ → S such that π(Pi) = Pi (where π(Pi) = {π(s) | s ∈ Pi}) is called a partial permutation over S = ∑i Pi.

Definition 3

• Given a CSP (Z, V,D,C), and partitions Z = ∑k≤r Pk, V = ∑l≤s Ql, we say that the CSP has partial variable and value symmetry iff all variables within each Pk and all values within each Ql are considered as symmetric.
• Given two assignments A and B on a partially symmetric CSP with single-valued variables, we say that A dominates B iff there exist partial permutations π over Z = ∑k≤r Pk and α over V = ∑l≤s Ql such that for all (X, v) ∈ A it holds that (π(X), α(v)) ∈ B.
• Given a partially symmetric set-CSP and setassignments A and B, we say that A dominates B iff there exist partial permutations π over Z = ∑k≤r Pk and α over V = ∑l≤s Ql such that A(π, α) ⊆ B, where A(π, α) := {(π(X), α(S))|(X, S) ∈ A}.
• Given two arbitrary (set-)assignments A and B for a partially symmetric (set-)CSP, we call the problem of determining if A dominates B the Dominance Detection Problem.

3 Symmetric Single-Valued Variables over Symmetric Values

The first general symmetry model that we study is powerful enough to manage symmetric single-valued variables over symmetric values. Throughout this section, we consider the partially symmetric CSP (Z, V, D, C) with single-valued variables. We assume also that we are given a partition of the variables ∑k≤r Pk = Z and a partition of the values ∑l≤s Ql = V such that all variables within each Pk and all values within each Ql are considered symmetric. Note that such partitions could be derived by a static analysis of a constraint program. The main objective in this section will be to show that there exists an effective symmetry breaking algorithm that runs in polynomial time for this scenario.

The key idea consists in the introduction of structural abstractions: to model a CSP, we need to uniquely label each value and each variable with a name - which is, of course, not natural when certain variables and certain values are actually indistinguishable. We can rectify this by viewing each variable and each value as a member of a symmetry class. In the beginning, these classes correspond directly to the sets Pk and Ql. When assignments are committed, though, some of those initial symmetries are broken. Then, in order to check which CSP objects are still indistinguishable, we need to introduce subclasses of the original symmetry classes. We will see that we can detect the remaining symmetries by labeling each of those subclasses with a certain signature that is defined by the set of initial symmetries and the given assignments. We will see also that it is really these signatures that capture our intuitive wish to abstract from the CSP model at hand to the actual structure of the problem.

3.1 Signatures

Consider the following example: We have variables X1, . . . ,X8 over domains D(X1) = · · · = D(X8) = {v1, . . . , v6}. Now assume that the first four and the last four variables are indistinguishable, i.e. P1 = {X1 . . . ,X4} and P2 = {X5, . . . ,X8}. Furthermore, assume that Q1 = {v1, . . . , v3}, Q2 = {v4, . . . , v6}, and that we are given the following two assignments: A1 = {(X1, v1), (X2, v1), (X3, v2), (X6, v5), (X7, v1), (X8, v2)} and A2 = {(X1, v6), (X2, v1), (X3, v2), (X4, v2), (X5, v1),- (X6, v6), (X7, v2), (X8, v2)}. See Figure 1(a) for an illustration. When looking at the first assignment, we see that: 1. There is one value (v1) in Q1 that is taken by two variables in P1 and one variable in P2. 2. There is one value (v2) in Q1 that is taken by one variable in P1 and one variable in P2. 3. There is one value (v5) in Q2 that is taken by one variable in P2. On the other hand, in the second assignment: I. There is one value (v2) in Q1 that is taken by two variables in P1 and two variables in P2. II. There is one value (v1) in Q1 that is taken by one variable in P1 and one variable in P2. III. There is one value (v6) in Q2 that is taken by one variable in P1 and one variable in P2. Lining up 1-I (v1 ↦ → v2, {X1,X2} ↦ → {X3,X4}, {X7} ↦ → {X7,X8}), 2-II (v2 ↦ → v1, {X3} ↦ → {X2}, {X8} ↦ → {X5}), and 3-III (v5 ↦ → v6, {X6} ↦ → {X6}), we see that A2 is structurally an assignment extended from A1, or, in other words, that A1 dominates A2 (see also Figure 1(b)).

What we have done in this small example is to abstract from the given model and the (arbitrary) names of variables and values to the actual structure of the problem. That is, instead of talking about specific variables and values, we considered members of classes. Specifically, for each assignment we implicitly assigned each value a signature that captures by how many members of each variable-symmetry class it was taken. For instance, in A1 v1 has the signature (2 ×P1, 1 ×P2), or, in shorter writing, the signature of v1 is sigA1 (v1) = (2, 1). In A2, on the other hand, the signature of v2 is sigA2 (v2) = (2, 2). Consequently, v2 in A2 can be viewed as more specialized than v1 in A1, or one may also say that v1 in A1 dominates v2 in A2. In this terminology, v1 in A2 has signature sigA2 (v1) = (1, 1) and therefore dominates v1 in A1. Note that sigA2 (v6) is also (1, 1), but that v6 in A2 does not dominate v1 in A1 since v6 ∈ Q2 whereas v1 ∈ Q1. In general:

Definition 4

• We say that a value v in an assignment A dominates a value w in assignment B iff v and w belong to the same value-symmetry class and sigA(v) ≤ sigB(w). 1
• We say that a value v in an assignment A is structurally equivalent to a value w in assignment B iff v and w belong to the same value-symmetry class and sigA(v) = sigB(w).

3.2 Dominance Detection Using Signatures

The following lemma shows how signature-abstractions can help to detect dominance relations among assignments:

Lemma 1

An assignment A dominates another assignment B in a partially symmetric CSP iff there exists a partial permutation α over ∑l≤s Ql such that v in A dominates α(v) in B for all v ∈ V .

Proof: First, let us assume that A dominates B. Then, there exist partial permutations π over ∑k≤r Pk and α over ∑l≤s Ql such that for all (X, v) ∈ A it holds that (π(X), α(v)) ∈ B. Since both X and π(X) belong to the same symmetry class, we have that for all values v ∈ V it is sigA(v) ≤ sigB(α(v)), which is the same as to say that v in A dominates α(v) in B. Now assume there exists a partial permutation α over ∑l≤s Ql such that sigA(v) ≤ sigB(α(v)) for all v ∈ V . Then, since each variable is assigned to at most one value, there exists a partial permutation π over ∑k≤r Pk such that for all (X, v) ∈ A it holds that (π(X), α(v)) ∈ B. Thus, we have that A dominates B.

Consequently, we have that A dominates B iff there exists a perfect matching in a bipartite graph where the edges are defined by the signature-relation of values (see Figure 1(b)):

1 Where the ≤-relation on vectors is defined as the usual component-wise comparison that yields to the so-called dominance ordering - which is different from a lexicographic ordering.

Definition 5

Given two assignments A and B, let us denote with V ′ a set of duplicates of the values in V by attaching a prime sign after the values' names (i.e. V ′ := {v ′ | v ∈ V }). Then, we define the dominance detection graph DDG(A, B) := (V ∪ V ′ , E) where E := {(v,w ′ ) | v in A dominates w in B} denotes the set of arcs.

Theorem 1

Given two assignments A and B over a CSP with partially symmetric single-valued variables and partially symmetric values, the dominance detection problem between A and B has complexity O(M + m 2 + mn), where M = O(m 2.5 ) is the time needed to determine whether there exists a perfect matching in DDG(A, B), m is the number of values, and n is the number of variables.

In the interest of space here and at many other occasions we must omit a formal proof. However, we would like to note that, with Lemma 1, it is clear that the dominance detection problem can be solved basically by determining whether there exists a perfect bipartite matching in DDG(A, B). The additional complexity denoted in the theorem is due to the necessity to construct DDG(A,B) first. It is obvious that this can be achieved in time O(nm 2 ), which already proves that symmetry breaking in this scenario is tractable. However, the runtime can be improved to the complexity that is claimed here by using sparse representations of signatures. Then, in the algorithm analysis we can exploit that the total number of non-zero signature components is bounded by O(|A| + |B|) = O(n).

Interestingly, it can also be shown that every bipartite graph can also be viewed as a dominance detection graph of a CSP and assignments A and B that can be determined in time linear in the size of the given graph. And therefore, a perfect bipartite matching exists iff A dominates B, which makes the dominance detection problem at least as hard as bipartite matching. In other words, we can show that dominance detection takes time T where T ∈ Ω(M)∩O(M+m 2 +mn).

4 Symmetry-Based Filtering

With Theorem 1, we can break all symmetries when given a CSP with partially symmetric variables and values in polynomial time when using a symmetry breaking by dominance detection (SBDD) approach [Fahle et al., 2001; Focacci and Milano, 2001]. What is annoying in this setting is that we still have to check every choice point to see if it is not dominated by one that was previously expanded, i.e. we still have to touch the garbage in order to see that it is garbage. We will now develop an algorithm that does not suffer from this disadvantage.

We achieve this goal by using dominance detection also for filtering rather than just pruning 2 . Obviously, a brute-force approach could simply try assignments out and use the dominance detection algorithm above to perform filtering as well. This procedure would lead to a very poor runtime, though. In the following, we will show that filtering based on symmetry can be performed much more efficiently.

Within SBDD, there exists a natural distinction between two types of filtering that apply: The first consists in making sure that none of the newly created children are symmetric to a node that was fully expanded before the node that is currently branching off. When applying unary branching constraints (which we assume are used here), this can be achieved by shrinking domain variables accordingly. The other, fundamentally different type of "filtering" consists in the creation of children that are also not symmetrical to each other. Both types need to be addressed to achieve a symmetry-free search tree (which corresponds to the GE-trees in [Roney-Dougal et al., 2004]). We distinguish the two types of filtering by naming them differently: symmetric-ancestor based filtering and symmetric-sibling based filtering.

Symmetric-Ancestor based Filtering

The goal of symmetric-ancestor based filtering is to shrink the domains such that instantiating a variable with one of its domain values will not result in the creation of a search node that is symmetric to one that was previously expanded.

Definition 6

Given a depth-first-search tree T , 3 we say that a choice point B (associated with its homonymous assignment B that captures previously committed unary branching decisions) is ancestor-symmetry resistant iff for all previously fully expanded nodes A ∈ T (A is called an ancestor of B) and for all variables X and values v ∈ D(X) it holds that A does not dominate B ∪ {(X, v)}.

Assume that we are currently investigating choice point B and that A is some ancestor node that does not dominate B. Observe that instantiating one more variable X ∈ Pk for some k by setting X ↦ → w ∈ Ql for some l will change only the signature of w from sigB(w) to sigB(w) + ek, where ek denotes the unit vector with a 1 in the kth component. We set B ′ := B ∪ {(X,w)}. Then, D1 := DDG(A,B)

2 With 'filtering', we refer to the idea of domain reduction in CP; 'pruning' refers to the detection of a sufficient reason to backtrack.

3 In the interest of space, we must omit a formal definition of a search tree here. The meaning should become clear from the context.

and D2 := DDG(A,B ′ ) only differ in that the latter bipartite graph may contain some additional edges that must all be incident to w ′ in the right partition. Obviously, if D2 contains an m-matching, this matching must contain exactly one of those additional edges. Consequently, if A dominates B ′ , then D1 must contain an m- 1-matching. Only if this is the case, work needs to be done to make B ancestor-symmetry resistant with respect to A.

So let us assume that D1 contains an m-1-matching. Provided with that matching, using some straight-forward matching theory we can identify efficiently those and only those additional edges that would allow us to transform the existing matching into a perfect one. Furthermore, it can also be shown that those critical edges are independent of the particular m- 1-matching that we computed (For an introduction to matching theory we refer to [Ahuja et al., 1993]). Among those critical edges that, if added, would allow us to construct an m-matching, the only ones that we need to consider are those which run between nodes v and w ′ with v, w ∈ Ql for some 1 ≤ l ≤ s and for which there exists 1 ≤ k ≤ r such that sigA(v) ≤ sigB(w) + ek. If and only if we find such a pair of nodes, a single extra assignment added to B will result in a successful dominance detection. Precisely, every assignment of w to a previously unassigned variable X ∈ Pk will result in a dominated choice point. Thus, if we remove w from the domain of X for all unassigned X ∈ Pk, we keep the unique parts of the search space and we never produce choice points that are symmetric to one that was expanded previously to B.

With Theorem 1, the runtime needed for the initial valuematching algorithm is bounded by O(m 2.5 +mn). We can also prove that a filtering algorithm can be formulated that, once the matching is computed, runs in time O(m 2 +mn). 4 Therefore, since within SBDD at most n(m - 1) ancestor nodes need to be considered, we can prove the following:

Theorem 2

Given a CSP with partially symmetric single-valued variables and partially symmetric values, we can achieve ancestor-symmetry resistance for a given search node in time O(nm 3.5 + n 2 m 2 ).

Symmetric-Sibling based Filtering

To achieve full symmetry prevention, we also need to guarantee that newly created siblings are not symmetric to each other. Therefore, after we choose the next variable to be assigned, but before we branch on it, we need to perform one more "filtering" step (it is actually more of an implicit pruning step) where we choose a single representative value out of each equivalence class of values which, when assigned to the chosen variable, would result in the creation of symmetric choice points. Due to the fact that, whenever a sibling dominates another, they both must already be structurally equivalent (see Definition 4), we can avoid producing symmetric siblings simply by choosing exactly one representative value among those that are structurally equivalent. The complexity of this filtering step is dominated by that of symmetricancestor based filtering.

4 Again, the main technical idea consists in the use of sparse signatures. The proof of the complexity is not particularly insightful but lengthy, which is why we leave it out here.

Putting ancestor and sibling-based filtering together, we have completed our development of an effective symmetry breaking algorithm for CSPs with partial single-valued variable and value symmetry that runs in polynomial time. Note that the practical performance of the algorithms sketched can be enhanced in practice: for example, it is fully sufficient to check against previously expanded nodes for which an m - 1 - h-maximum matching was found only after variable instantiations to h different values have been committed. And as usual, by considering incremental updates of matchings, memory can be traded for cpu-time.

5 Limits of Efficient Dominance Detection

After having developed a polynomial symmetry breaking algorithm for CSPs with partially symmetric single-valued variables in the presence of partial value symmetry, we now show that dominance detection for partially symmetric set variables in the presence of partial value symmetry is NP-hard. More precisely, we reduce the corresponding dominance detection problem to subgraph-isomorphism.

In order to achieve the desired reduction we construct a set-assignment from a graph in the following way:

Definition 7

Given an undirected graph G = (V,E) with c := |V |, we define a set of symmetric values N := {n1, ..., nc}, and a set of symmetric variables P := {pij|{i, j} ∈ E}. Then, the set-assignment A(G) is defined as A(G) := {(pij , {ni, nj}) | {i, j} ∈ E}.

Theorem 3

Given two undirected graphs G1 = (V,E1) and G2 = (V,E2), G1 is sub-isomorphic to G2 iff A(G1) dominates A(G2) when all variables and values are considered to be symmetric.

Proof: We start by showing that A(G1) dominates A(G2) if G1 is sub-isomorphic to G2. Let σ : V ↦ → V bijective such that {i, j} ∈ E1 implies {σ(i), σ(j)} ∈ E2. Then, for all (pij, {ni, nj}) ∈ A(G1) it holds that (pσ(i),σ(j), {nσ(i), nσ(j)}) ∈ A(G2). Therefore, A(G1) dominates A(G2).

Now let us assume that A(G1) dominates A(G2). Then, there exist functions π : E1 ↦ →E2 and α : V ↦ → V such that (pij , {ni, nj}) ∈ A(G1) implies (pπ({i,j}), {nα(i), nα(j)}) ∈ A(G2). By construction of A(G2), this is equivalent to {nα(i), nα(j)} ∈ E for all {i, j} ∈ E. Thus, α is a subisomorphism between G1 and G2.

With Theorem 3, it is easy to prove the following

Corollary 1

The dominance detection problem over partially symmetric set variables and partially symmetric values is NP-hard.

Proof: We reduce the problem to subgraph-isomorphism. In order to apply Theorem 3, we need to ensure that both graphs operate over the same set of nodes. In case that the set of nodes of the given graphs differ, it is easy to see that G1 cannot be sub-isomorphic to G2 if G1 contains more nodes than G2. In case that G1 actually contains fewer nodes than G2, it is easy to see that we can add isolated nodes to G1 without affecting subgraph-isomorphism. Then, we have that both graphs contain the same number of nodes, and by relabelling the nodes in both graphs, we may assume that both graphs operate on the same set of nodes.

Note that, despite this negative result, in some important special cases the symmetry detection problem for CSPs with partially symmetric set variables and values is still tractable. For instance, when the set variables cannot overlap, the algorithm developed in Section 3 can be adapted easily (by simply exchanging the roles of values and variables) to break all symmetries efficiently.

Corollary 2

The dominance detection problem over partially symmetric non-overlapping set variables and partially symmetric values is tractable.

Note that the dominance detection problem as we consider it here regards arbitrary assignments. This implies that, when the detection problem is tractable, we can break symmetries efficiently. However, the situation changes when we achieve an intractability result like the previous one: Within methods like SBDD the assignments that need to be compared can only differ in a rather specific fashion. We can also show that these more specific dominance detection problems are NPhard as well, therefore proving that SBDD in its general form is incapable of breaking symmetries in partially symmetric set-CSPs efficiently. However, we would like to stress that this result does not imply that symmetry breaking is NP-hard in general since we do not consider other methods here like remodeling or the adaption of the branching scheme.

6 Higher Forms of Symmetry

Note that our intractability proof above shows that dominance detection over symmetric set variables and symmetric values is already NP-hard when there exists only one set of symmetric set variables and one set of symmetric values. Clearly, the problem stays NP-hard when we allow partial symmetry. Partial symmetry is very helpful when even more complicated forms of symmetry need to be handled. Consider for example the Social Golfer Problem (SGP):

32 golfers want to play in 8 groups of 4 each week, such that any two golfers play in the same group at most once. How many weeks can they do this for? 5

The problem can be generalized by parameterizing it to g groups of s players each, playing for w weeks (instances are usually written in g-s-w-format). A common model for the problem introduces a set variable for each group, so that intragroup symmetries are broken automatically. Groups within the same week are symmetric, and furthermore, whole weeks are also symmetric, i.e. whole sets of set variables are symmetric to other sets of set variables. We can model this by introducing new week-values, one of which each group must be assigned to. Consider the assignment to an SGP instance 3-2-2 given in Table 1: By introducing two week-values W1 and W2 to one of which each group-variable is assigned upon instantiation, we can model the SGP as a dominance detection problem over symmetric set variables and partially symmetric values (see Figure 2). By means of this little trick, higher forms of symmetry can be reduced to symmetric set variables over partially symmetric values, which makes the corresponding dominance detection problem a most relevant research subject. We believe that developing fast algorithms that (approximately) solve this NP-hard problem should be a focus of symmetry breaking research at this point.

5 Problem 10 in CSPLib - http://www.csplib.org/.

7 Conclusion

When breaking symmetry by dominance detection, a computationally efficient symmetry breaking scheme can be achieved if we can solve the dominance detection problem in polynomial time. Therefore, we studied the complexity of dominance detection between arbitrary assignments for combined variable and value symmetry. For CSPs with partially symmetric single-valued variables and partially symmetric values we developed an efficient dominance detection algorithm that shaves the search-tree to a point where no two search-nodes can be symmetrical to each other. In contrast to these positive tractability results, for set-CSPs with symmetric variables and symmetric values, we found that the dominance detection problem is NP-hard.

Our algorithms are based on the structural abstraction of a given CSP, a method that we refer to as structural symmetry breaking (SSB). When only the structure of variables and values that partition into whole equivalence classes of pairwise symmetric elements is considered, the work presented here effectively closes the outstanding complexity questions regarding SBDD. Further research will have to regard CSPs whose symmetry structures are more refined. Consider for example the case where the variables form a ring structure and all rotations on the ring yield to an equivalent CSP. Under what conditions can we break value and variable symmetry when the permutations on the CSP elements form structures that are different from partitions?

In our view, it is perceivable that structural symmetries could be derived automatically by a static analysis of a given constraint program if the modeling language used provided semantics regarding symmetries. For instance, an alldifferent constraint could provide the information that all variables and values are treated as symmetric by this constraint. Then, built-in efficient dominance detection algorithms like the one that we developed can be used efficiently to break the symmetries that were derived automatically, thus making symmetry breaking an effective and efficient component of constraint programming that is totally seamless for the user.

Acknowledgments

Many thanks to Pierre Flener and Justin Pearson for helping tremendously in polishing up the presentation of this work!