Information Technology Reference
In-Depth Information
Given a collection
S
of literals, the
pointwise
stabiliser of
S
is the subgroup
of
G
which stabilises each element of
S
individually. The
setwise
stabiliser of
S
is the subgroup of
G
that consists of symmetries mapping the set
S
to itself.
Definition 7.
A
GE-tree
(group equivalence tree) for a CSP with symmetry
group
G
is any search tree
T
satisfying the following two axioms:
1. No node of
T
is isomorphic under
G
to any other node.
2. Given a full assignment
A
, there is at least one leaf of
T
which lies in the
orbit of
A
under
G
.
Therefore, the nodes of
T
are representatives for entire orbits of partial as-
signments under the group, and the action of the group on the tree fixes every
node. Of course, a GE-tree will be constructed dynamically, and the constraints
of a CSP will generally prevent us from searching the whole of
T
. We define
a GE-tree to be
minimal
if the deletion of any node (and its descendants) will
delete at least one full assignment.
One of the main results in [10] is a constructive proof of the following Theo-
rem:
Theorem 1.
Let
L
be a CSP with only value symmetries. Then breaking all
symmetries of
L
is tractable.
The theorem is proved by giving a low-degree polynomial algorithm which
constructs a minimal GE-tree for
L
. This algorithm is summarized as follows:
At each node
in the search tree do:
Compute the pointwise stabiliser
G
(Val(
N
))
of Val(
N
N
).
Select a variable
X
N
).
Compute the orbits of
G
(Val(
N
))
on Dom(
X
).
For each orbit
which is not in Var(
do:
Construct a downedge from
O
N
labelled with an element from
O
.
End for.
End for.
It is shown in [10] that this can all be done in low-degree polynomial time. The
result of only considering this reduced set of edges is that no two nodes in the
resulting tree will be equivalent to each other under the subgroup of
G
that
consists of value symmetries.
This theorem has the following immediate corollary:
Corollary 1.
Let
L
be any CSP with symmetry group
G
. Then breaking the
subgroup of
G
that consists only of value symmetries is tractable (i.e. can be
done in polynomial time).
This begs the question: how may we break the remaining symmetries of a CSP?
For certain groups of variable symmetries, such as the full symmetric group,
the direct product of two symmetric groups, and the wreath product of two
Search WWH ::
Custom Search