论文标题
具有限制组成因子的组的超图同构
Hypergraph Isomorphism for Groups with Restricted Composition Factors
论文作者
论文摘要
我们认为，在同一组顶点$ v $上进行两次输入的超图形问题是输入的两个超图和一个置换组$γ$，而不是域$ v $，并且询问是否有γ$中的排列$γ\inγ$证明这两个超级分类是同构的。我们表明，对于输入组，所有其组成因素均与对称组的子组同构为$ D $点，可以在时间$ $ $ $（n+m）^{o（（（\ log d）^{c}^{c}}} $中解决这个绝对常数$ c $ n $ n $表示Vertices和$ m $ m $ mutther nordys $ n norked。特别是，这总体上提供了当前最快的同构测试。由于Schweitzer和Wiebking（STOC 2019），以前针对此问题的最佳算法是$ n^{o（d）} m^{o（1）} $。 作为此结果的应用，我们将图形的算法测试同构算法不包括$ k_ {3，h} $（$ h \ geq 3 $）作为未成年人的次要时间$ n^{o（（\ log h）^{c}}）} $。特别是，这给出了欧拉属图的同构测试，最多是$ g $在时间上运行的$ n^{o（（\ log g）^{c} {c}）} $。
We consider the isomorphism problem for hypergraphs taking as input two hypergraphs over the same set of vertices $V$ and a permutation group $Γ$ over domain $V$, and asking whether there is a permutation $γ\in Γ$ that proves the two hypergraphs to be isomorphic. We show that for input groups, all of whose composition factors are isomorphic to a subgroup of the symmetric group on $d$ points, this problem can be solved in time $(n+m)^{O((\log d)^{c})}$ for some absolute constant $c$ where $n$ denotes the number of vertices and $m$ the number of hyperedges. In particular, this gives the currently fastest isomorphism test for hypergraphs in general. The previous best algorithm for this problem due to Schweitzer and Wiebking (STOC 2019) runs in time $n^{O(d)}m^{O(1)}$. As an application of this result, we obtain, for example, an algorithm testing isomorphism of graphs excluding $K_{3,h}$ ($h \geq 3$) as a minor in time $n^{O((\log h)^{c})}$. In particular, this gives an isomorphism test for graphs of Euler genus at most $g$ running in time $n^{O((\log g)^{c})}$.
