已实现Schreier-Sims算法，如何用其稳定化子链剪枝中心化子搜索？

Great question—since you already have Schreier-Sims up and running, using that stabilizer chain to prune your centralizer and conjugacy class searches is exactly the right move to ditch brute-force inefficiency. Let’s break this down clearly, with practical steps tied to the graph automorphism context you’re familiar with.

First, a quick recap: the centralizer $C_G(g)$ of an element $g \in G$ is all $h \in G$ where $hg = gh$. Your Schreier-Sims stabilizer chain ($G = G_0 \supseteq G_1 \supseteq ... \supseteq G_n = {e}$, where $G_i$ stabilizes the first $i$ points/vertices) lets you build valid $h$ incrementally while pruning impossible candidates at every step.

Here’s how to implement it:

• Recursive, constraint-driven extension: Build $h$ level by level, starting from the full group $G_0$. At each level $i$, you’re extending an element $h' \in G_i$ (which fixes vertices 1..i) to an element $h \in G_{i-1}$ (which fixes 1..i-1 and maps vertex $i$ to some candidate in its orbit under $G_{i-1}$).
• Key pruning constraint: For the candidate image $m$ of vertex $i$ (i.e., $h(i) = m$), enforce the commutativity rule $hg = gh$ for this vertex. Specifically:
  • If $g(i)$ is in the set 1..i-1 (which $h$ already fixes), then $h(g(i)) = g(i)$. This means $g(m) = g(i)$, so $m$ must equal $i$ (since $g$ is a permutation). No need to iterate over the entire orbit here—only $i$ is valid!
  • If $g(i)$ is outside 1..i-1, then $h(g(i))$ must equal $g(m)$. Since $h$ will eventually be a group element, $g(m)$ must lie in the orbit of $g(i)$ under $G_i$, which narrows down your candidate $m$ list.
• Recurse with updated group: Once you pick a valid $m$, represent $h$ as $t \cdot h'$, where $t$ is a transversal element mapping $i$ to $m$. Now you need to find $h' \in G_i$ such that $h'$ commutes with $t^{-1}gt$ (since $hg = gh$ implies $h'(t^{-1}gt) = (t^{-1}gt)h'$). This reduces the problem to a smaller group $G_i$, cutting the search space drastically.

The conjugacy class of $g \in G$ is all elements of the form $hgh^{-1}$ for $h \in G$. Again, the stabilizer chain lets you generate distinct conjugates without redundant work.

Practical steps:

• Leverage transversals to avoid redundancy: For each level $i$ in your chain, use the transversal $T_{i-1}$ (elements mapping $i$ to distinct orbit points) instead of the entire group $G_{i-1}$. Conjugating $g$ by elements of $G_i$ will produce conjugates within the smaller group $G_i$, which you can handle recursively—no need to waste time on those first.
• Prune duplicate conjugates: If two transversal elements $t_1$ and $t_2$ produce conjugates $t_1gt_1^{-1}$ and $t_2gt_2^{-1}$ that are already conjugate in $G_i$, you can skip one. To check this, verify if $t_2^{-1}t_1$ is in $C_G(g) \cap G_{i-1}$—if so, the two conjugates are identical, so you can discard one candidate.
• Recursive generation: For each valid $t \in T_{i-1}$, compute $tgt^{-1}$, then recursively find all conjugates of this element in $G_i$. This builds the full conjugacy class by combining top-level transversal conjugates with lower-level recursive results.

Since you’re familiar with searching $S_n$ for graph automorphisms, think of $G$ as your graph’s automorphism group (which you can compute with Schreier-Sims). The stabilizer chain here is built around graph vertices, so you can layer on adjacency-preserving constraints alongside the centralizer/conjugacy rules:

• When picking a candidate image $m$ for vertex $i$, not only must it satisfy the commutativity/conjugacy constraints, but it must also have the same adjacency pattern as $i$ (same neighbors, same degree). This adds another layer of pruning to your candidate list.
• For example, if $g$ maps vertex $i$ to a neighbor of $i$, then $h(g(i)) = g(h(i))$ implies $h(i)$ must map to a neighbor of $g(h(i))$, which aligns with the graph’s structure to eliminate invalid candidates quickly.

内容的提问来源于stack exchange，提问作者dcrewi