论文标题
用于图同构的多项式平行算法，使用Quasipolynomial数量的处理器
A polynomial time parallel algorithm for graph isomorphism using a quasipolynomial number of processors
论文作者
论文摘要
图形同构（GI）问题是一个理论上有趣的问题，因为尚未证明它在P中也不是NP完整的问题。 Babai在2015年宣布针对GI问题的准化性时间算法时取得了突破。 Babai的作品为GI提供了最有效的算法，并且有充分的证据有利于gi $ \ ne $ np和p $ \ ne $ np的想法。基于Babai的算法，我们证明GI可以通过使用准精液数量的处理器在多项式时间内运行的平行算法进一步求解。我们通过识别Babai算法中的瓶颈并使它们并行实现这一结果。特别是，我们证明可以使用多项式的处理器在平行的对数时间中计算颜色完善，并且可以使用quasipolynomial量的处理器在平行的多项式时间内计算$ k $维的WL细化。我们的工作表明，可以在平行计算机中有效地计算图形同构和GI完整问题，并提供有关在实践中加速并行GI程序的见解。
The Graph Isomorphism (GI) problem is a theoretically interesting problem because it has not been proven to be in P nor to be NP-complete. Babai made a breakthrough in 2015 when announcing a quasipolynomial time algorithm for GI problem. Babai's work gives the most theoretically efficient algorithm for GI, as well as a strong evidence favoring the idea that class GI $\ne$ NP and thus P $\ne$ NP. Based on Babai's algorithm, we prove that GI can further be solved by a parallel algorithm that runs in polynomial time using a quasipolynomial number of processors. We achieve that result by identifying the bottlenecks in Babai's algorithms and parallelizing them. In particular, we prove that color refinement can be computed in parallel logarithmic time using a polynomial number of processors, and the $k$-dimensional WL refinement can be computed in parallel polynomial time using a quasipolynomial number of processors. Our work suggests that Graph Isomorphism and GI-complete problems can be computed efficiently in a parallel computer, and provides insights on speeding up parallel GI programs in practice.
