Precision and complexity of the computations that are needed to solve the graphs isomoprhism problem by equality check of polynomials
Purpose. To show that graph modified characteristic n-variable polynomial may be used to obtain an algorithm to numerically solve the graph isomorphism problem in the general case. Methodology. We use methods of graph theory, linear algebra as well as numerical methods of linear algebra combined with the elements of group theory. Findings. We present an algorithm for the graph isomorphism problem and show that it may be implemented numerically. For graphs on n vertices, we prove that the equality checking the values of the graphs modified characteristic polynomials at the predefined points may be implemented in O(n 4 ) time, although such polynomial of n variables has 2 n coefficients and this fact makes direct computations of the polynomial value impossible in some point with the required accuracy in polynomial time. We also prove that to do this checking we need machine numbers with O(n 2 ) mantissas length. It is shown that the algorithm may be seen as the process of the graphs modifications in the course of which we reduce cardinalities of automorphisms groups of the graphs that we obtained. Thus we reduce the time that is needed to solve the individual problems using presented backtracking scheme of the algorithm. We show that probability of a mistake for the algorithm is negligible if parameter of the algorithm is sufficiently large. Originality/value. The new complete graph invariant is considered and it is proved that it may be used to solve the graph isomorphism problem numerically.