Reduction of the graph isomorphism problem to equality checking of $n$-variables polynomials and the algorithms that use the reduction

Alexander Prolubnikov

The graph isomorphism problem is considered. We assign modified $n$-variable characteristic polynomials for graphs and reduce the graph isomorphism problem to the problem of the po…