论文标题
图形的直接产品原始测试是GI-HARD
Direct Product Primality Testing of Graphs is GI-hard
论文作者
论文摘要
我们研究了与直接产物（也称为Kronecker，Cardinal或Tensor产品）相对于图形原始测试问题的计算复杂性。在[1]中，Imrich证明，可以在多项式时间内确定（有限）连接和非分数图的原始测试和唯一的质量分解。作者将其作为一个开放的问题指出，如何导致非双分化，连接图的直接乘积扩展到双方连接的图并断开连接的图。在本文中，我们通过证明图形同构问题是多项式时间多个可降低的，可以降低图形综合测试问题（图上图上测试问题的补充），从而部分回答了这个问题。由于这个结果，我们证明了图同构问题是可简化原始测试问题的多项式时间图。我们的结果表明，连接性在确定图映射测试问题的计算复杂性方面起着至关重要的作用。
We investigate the computational complexity of the graph primality testing problem with respect to the direct product (also known as Kronecker, cardinal or tensor product). In [1] Imrich proves that both primality testing and a unique prime factorization can be determined in polynomial time for (finite) connected and nonbipartite graphs. The author states as an open problem how results on the direct product of nonbipartite, connected graphs extend to bipartite connected graphs and to disconnected ones. In this paper we partially answer this question by proving that the graph isomorphism problem is polynomial-time many-one reducible to the graph compositeness testing problem (the complement of the graph primality testing problem). As a consequence of this result, we prove that the graph isomorphism problem is polynomial-time Turing reducible to the primality testing problem. Our results show that connectedness plays a crucial role in determining the computational complexity of the graph primality testing problem.
