论文标题
具有对称树木的搜索问题：近乎最佳的个体化遍历算法的最佳遍历策略
Search Problems in Trees with Symmetries: near optimal traversal strategies for individualization-refinement algorithms
论文作者
论文摘要
我们在树上定义了一个搜索问题，该问题紧密捕获了所有当前实际图同构算法的回溯行为。给定两棵带有彩色叶子的树，目标是找到两叶相匹配的颜色，每棵树中都有一个。树木具有不变特性，该特性承诺，对于每对相等颜色的叶子，必须有一个对称性（或同构）将一片叶映射到另一片叶子。 我们描述了一种带有错误的随机算法，其中访问的叶子的数量在两棵树较小的大小的平方根中为quasilinear。对于有界程度的输入，我们开发了具有相似运行时间的拉斯维加斯算法。 我们证明这些结果是对数因素的最佳选择。我们在界面的输入上显示了一个随机算法的下限，该算法是树大小的平方根。对于无界程度的输入，我们显示了拉斯维加斯算法的线性下限。对于确定性算法，我们可以证明即使对于有界程度的输入，也可以证明线性结合。这表明了为什么随机算法优于确定性算法。 我们的结果解释了为什么同构工具痕迹的随机“与实验路径间的广度优先”（Piperno 2008）通常优于Nauty（McKay 1977）或Bliss等其他工具的深度优先搜索策略（Junttiltila，Kaski，Kaski 2007）。但是，我们的算法还提供了一种新的遍历策略，从理论上讲，与以前使用的遍历策略相比，它几乎是最佳的，最差的案例行为更好。
We define a search problem on trees that closely captures the backtracking behavior of all current practical graph isomorphism algorithms. Given two trees with colored leaves, the goal is to find two leaves of matching color, one in each of the trees. The trees are subject to an invariance property which promises that for every pair of leaves of equal color there must be a symmetry (or an isomorphism) that maps one leaf to the other. We describe a randomized algorithm with errors for which the number of visited leaves is quasilinear in the square root of the size of the smaller of the two trees. For inputs of bounded degree, we develop a Las Vegas algorithm with a similar running time. We prove that these results are optimal up to logarithmic factors. We show a lower bound for randomized algorithms on inputs of bounded degree that is the square root of the tree sizes. For inputs of unbounded degree, we show a linear lower bound for Las Vegas algorithms. For deterministic algorithms we can prove a linear bound even for inputs of bounded degree. This shows why randomized algorithms outperform deterministic ones. Our results explain why the randomized "breadth-first with intermixed experimental path" search strategy of the isomorphism tool Traces (Piperno 2008) is often superior to the depth-first search strategy of other tools such as nauty (McKay 1977) or bliss (Junttila, Kaski 2007). However, our algorithm also provides a new traversal strategy, which is theoretically near optimal with better worst case behavior than traversal strategies that have previously been used.
