The graph isomorphism problem is considered. We assign modi ed characteristic polynomials for graphs and reduce the graph isomorphism problem to the following one. It is required to nd out, is there such an enumeration of the graphs vertices that the polynomials of the graphs are equal. We present algorithms that use the redution and we show that we may check equality of the graphs polynomials values at speci ed points without direct evaluation of the values. We give justi cation of the algorithms and give the scheme of its numerical realization. The example of the approach implementation and the results of computational experiments are presented.
(A(G))ij = { 1; if (i; j) 2 E(G);
0; else: Let A(G) and A(H) be adjacency matrices of the graphs G and H. Then
G ≃ H , 9φ 2 Sn : A(H) = PφA(G)Pφ⊤; Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org where Sn is a symmetric group on [n] and (Pφ)ij = { 1; if i = φ(j);
0; else: By this formulation of the problem, the two graphs are isomorphic if and only if we can obtain adjacency matrix of the rst graph from adjacency matrix of the second one by some permutation of its rows and columns.
GI is one of the fundamental problems of discrete mathematics and there are numerous applications where it arises. For example, without solving GI, we cannot practically solve the following problem. In the problem we need to nd an n-vertices graph that has some speci ed property. We may search the graph doing the exhaustive search on all labelled n-vertices graphs. But, since there are n! of isomorphic labelled graphs, we must check the property only for nonisomorphic labeled graphs during this search. For this purpose, we need to efficiently solve GI. Else our memory expenses would be too high.
GI belongs to N P class since it takes O(n2) time to check whether some bijection of V (G) onto V (H) is an isomorphism. It is not proved that the problem is N P -complete and there is no any polynomial algorithm has been obtained for the general case of the problem.
GI is solvable in polynomial time for some classes of graphs: for trees [1], for graphs with bounded genus [2], for graphs with bounded multiplicity of their adjacency matrix eigenvalues [3], for graphs with bounded degree of their vertices [4] and for some other restricted classes of graphs. The more regular structure of the graphs, the harder to obtain solution of GI for them. Such classes as regular graphs, strongly regular graphs, isoregular graphs give the instances of GI that cannot be solved in polynomial time by existing algorithms.
For GI, the designed algorithms may be divided in two classes. The rst class algorithms are designed to solve GI for some restricted cases and the second class algorithms are designed to solve the problem for the general case. The examples of the algorithms which belongs to the rst class are the algorithms that solve GI for the mentioned above classes of graphs. The Ullman algorithm [5], the Schmidt-Druffel algorithm [6], B. McKay's NAUTY algorithm [7] belong to the second class of the algorithms. These algorithms are called practical, since they are exponential in the worst case but they are effective for most of the input graphs.
It stated in [8] that GI may be solved in quasipolynomial time. It is in the process of proof-checking by other mathematicians at the moment when this paper is written.
To solve GI, the algorithms checks graph invariants during their implementation. Graph invariants are properties of graphs which are invariant under graph isomorphisms, i.e., graph invariant is a function f such that f (G) = f (H) if G ≃ H. The examples of graph invariants are such graph properties as connectivity, genus, degree sequence, the characteristic polynomial of adjacency matrix, its spectrum. A graph invariant f (G) is called complete if the equality f (G) = f (H) implies that G ≃ H. Let us consider some of the well-known graph invariants.
The Weisfeiler-Lehman method is an example of the approach to check invariant characteristics of graphs. Applying this method, we perform iterative classi cation of graphs vertices. As a result, we have such colourings of vertices that we may use it to distinguish non-isomorphic graphs. Using this method, we can solve GI for large class of graphs in polynomial time. But it is shown [9] that there exists such pairs of nonisomorphic graphs on n vertices that they are cannot be distinguished by k-dimensional Weisfeiler-Lehman algorithm in polynomial time for k = Ω(n). This implies that, for the general case, this method not solve GI in polynomial time.
The procedures of graph canonization give complete graph invariants. For a graph G, using some procedure of graph canonization, we obtain its canonical form that is some labeled graph. Two graphs are isomorphic if and only if they have the same canonical form. Using canonical form of the graph, we may compute its canonical code. Canonical code c(G) of a graph G is a bit string such that G ≃ H if and only if c(G) = c(H). The example of a canonical code is the code c0(G):
c0(G) = m2aSxnf(A) (
In [11], complete invariant for hypergraphs is presented. This complete invariant is not a result of canonization. For the case of simple graphs, this invariant is a system of n2 + 1 polynomials over a eld of characteristic q, where q is a prime number or zero.
In our work, we assign modi ed characteristic polynomials for graphs and reduce the graph isomorphism problem to the following one. It is required to nd out, is there such an enumeration of the graphs vertices that the modi ed characteristic polynomials of the graphs are equal. The modi ed characteristic polynomial of a graph is not a graph invariant in the sense of its immutability to different enumerations of the graph vertices. But the polynomial is complete invariant of a graph in the sense that there is no such enumeration that gives equal polynomials for non-isomorphic graphs.
In addition to the reduction and the theoretical algorithm that we have presented in [12], using the same approach, we present the practical algorithms for GI in this work. These algorithms not check equality of the graphs polynomials by checking equality of their coefficients but they check equality of the polynomials values in randomly taken points. We give justi cation of the algorithms and give the scheme of its numerical realization. The example of the approach implementation and the results of computational experiments are presented. 2
The modi ed characteristic polynomial of a graph Let us consider the characteristic polynomial of a graph and some of its modi cations which have been used for characterization of graphs by their structural properties. The characteristic polynomial of a graph G is the polynomial
G(x) = det(A(G) xE); where x is a variable and E is the identity matrix. Let D(G) = diag(d1; : : : ; dn) be a diagonal matrix, where di is a degree of vertex i 2 V (G).
Some modi cations of the characteristic polynomial are considered in [13]. The examples are the graph Laplacian L(G) that is de ned as the signless graph Laplacian jL(G)j that is de ned as
L(G) = D(G)
A(G); jL(G)j = D(G) + A(G); and some other modi cations which may be generalized by the polynomial G(x; y): G(x; y) = det(xE (A(G) yD(G))):
Seidel polynomial [14] is another modi cation of the characteristic polynomial that is obtained by modi cation of a graph adjacency matrix. It is the polynomial G(x): G(x) = det(xE (F
E 2A(G))); where (F )ij = 1 for i; j = 1; n.
A generalization of the characteristic polynomial is the polynomial that is presented in [15]. It is a polynomial G(x; y; ) of the form
G(x; y; ) = det(A(x; y)
E); where A(x; y) is the matrix, derived from A, in which the 1s are replaced by variable x and 0s (other than the diagonals) are replaced by variable y.
None of the presented above modi cations of the characteristic polynomial is a complete graph invariant.
The modi ed characteristic polynomial of a graph. Variables of the polynomials above have no connection with graph vertices. We modify the characteristic polynomial G(x) of a graph G on n vertices assigning variable xi to i 2 V (G). Let x1; : : : ; xn be independent variables and let X = diag(x1; : : : ; xn).
De nition 1. For a graph G, jV (G)j = n, G(x1; : : : ; xn) is a polynomial of the form
G(x1; : : : ; xn) = det(A(G) + X):
(
For graphs on n = 1; 2; 3 vertices, the polynomials of the form (
For a subset c of V (G), let xc be a product of the form ∏i2c xi and A(G)c be a
determinant of the submatrix of A(G) that is obtained by deleting of the rows and
columns of A(G) where numbers are belong to the subset c. A(G)c is the coefficient of
∏i2c xi in the polynomial G(x1; : : : ; xn). Having c and φ 2 Sn, let φ(c) be the image
of c: φ(c) = fφ(i) j i 2 cg. For x = (x1; : : : ; xn), xφ = (xφ(
Theorem 1. G ≃ H and φ : V (G) ! V (H) is an isomorphism of the graphs if and only if
G(x1; : : : ; xn) = H(xφ(
Proof. If G ≃ H and φ is an isomorphism of the graphs, then (
A(H) = PφA(G)Pφ⊤; and the coefficients of G and H, corresponded by φ, are equal to each other.
Let us show that if the equality (
If (
The algorithms for GI that check equality of the values of
the modi ed characteristic polynomials at the speci ed
points
To check wether the two given graphs G and H are isomorphic, we try to nd φ such
that the equality (
The equality checking of coefficients of two polynomials of the form (
The Direct algorithm for GI
Let N 2 N, S = fk=10N j 0 < k < 10N ; k 2 Z+g, S (0; 1). For i = 1; n, let "i be selected
at random independently and uniformly from S. Let "(i) be the following points of Rn:
"(0) := 0, "(i) := "(i 1) + "iei, i = 1; : : : ; n. I.e., "(
In the course of implemetation of the algorithms we present below, we trying to set a bijection φ : V (G) ! V (H) such that G("(i)) = H ("(φi)). On the i-th iteration of the Direct algorithm, we searching for such j 2 V (H) that If we can set such φ for the graphs G and H during iterations of the algorithm, we make a conclusion that the graphs are isomorphic and φ is an isomorphism of the graphs, else we make a conclusion that they are not isomorphic.
The Direct algorithm for GI is named below as Algorithm 1. It is a test for isomorphism that may be mistaken for some instances of GI. For any test for isomorphism, there are two kinds of mistakes it can make: 1) wrong conclusion that G ≃ H, when G ̸≃ H, 2) wrong conclusion that G ̸≃ H, when G ≃ H. As it shall be stated below, the probability of a mistake of the rst kind may be considered as negligible for the Direct algorithm. The algorithm solves the GI instances that presented in [16] but it makes a mistake of the second kind for GI instances obtained for strongly-regular graphs from [17] when n 13.
Algorithm 1 (G; H) 1 J V (H); 2 for i 1 to n 3 choose at random "i 2 S; 4 if (9j 2 J : G("(i)) = H ("(φi 1) + "iej )) 5 φ(i) j; 6 J J nfjg; 7 else print "G ̸≃ H". 8 print "G ≃ H, φ is an isomorphism of G and H". 3.2
Recursive modi cation of the Direct algorithm for GI Algorithm 2 we present below is a recursive modi cation of the Direct algorithm for GI. In addition to the GI instances that presented in [16], in a reasonable time, it solves the GI instances obtained for strongly-regular graphs from [17] (n 64). true; k, where k such that J = fkg;
The recursive procedure Set the correspondence gets on input i 2 V (G) and
set φ(i) j for j 2 J V (H) such that (
The probability of mistake. Let P[ ] denote a probability of the event that we specify in square brackets. The following theorem [18, ?] is known: Theorem 2. Let f 2 F [x1; : : : ; xn] be a non-zero polynomial of total degree d 0 over a eld F . Let S be a nite subset of F and let "1; : : : ; "n be selected at random independently and uniformly from S. Then
P[f ("1; : : : ; "n) = 0] d jSj : If we have set up φ for every i = 1; : : : ; n, then Let G("1; : : : ; "n) =
H ("φ(
H ("φ(
The numerical realization of the algorithms
and their computational complexity
Modi cations of adjacency matrices. Let d be the maximum degree of vertices of G and
H: d = maxfd1; : : : ; dng (we suppose that G and H have the same degree sequences).
Let A and B be modi ed graph adjacency matrices of the following form
A := A(G) + 2dE; B := A(H) + 2dE:
(
H (xφ(
We may consider the presented algorithms as a try to perform series of consistent modi cations of the matrices A and B:
A(i) := A(i 1) + "iEi; B(i) := B(i 1) + "iEj ;
where A(0) = A; B(0) = B, i = 1; : : : ; n. We call the modi cations of the form (
A(ii)
f g (B(i 1) + "iEj )fjg = ((B(i 1) + "iEj ) 1)jj ;
det A(i) = det(B(i 1) + "iEj )
(
Eliminating regularities of graphs and reducing the exhaustive search The Algorithm 2 scheme differs from the scheme of exhaustive search on all bijections of V (G) onto V (H) only in step 8 of the procedure Set the correspondence that it use. Here, in addition to check whether current j 2 V (H) is not already setted up as an image for some vertex in V (G) with label less than i, we check equality of the polynomials values in prede ned points "(i) and "(φi). The algorithm of the same form may be obtained for numerous graph invariant characteristics. For example, we may check the equality of adjacency matrices of the induced subgraphs on i vertices for both input graphs. These subgraphs include the vertices for which the correspondence is setted up and all of the edges whose endpoints are these vertices. We check the equality of the subgraphs adjacency matrices after enumerating vertices of the induced subgraph of H in according to φ that is setted up for vertices from V (G) with labels less or equal than i.
The graph G has more regular structure if it has more symmetries, i.e., if there are such bijections of V (G) onto V (G) which are isomorphisms of G onto itself (graph automorphisms). De nition 2. The graph G automorphism group is a set of isomorphisms of the graphs onto itself, i.e.,
Aut(G) = f 2 Sn j aij = a (i) (j); i; j = 1; ng: De nition 3. The orbit of the vertex i 2 V (G) is the set
Oi(G) = f (i) j 2 Aut(G)g: The considered scheme of the algorithm for GI (exhaustive search on all bijections that is reduced by equlity checking of some invariant characteristics for the input graphs) may be modi ed to be efficient for some restricted classes of graphs, or, using some invariant characteristics, we may obtain some partitions of the graphs vertices that we may use to reduce the exhaustive search, but the main problem stays the same for every algorithm for GI of that sort: the more cardinalities of Aut(G) and Aut(H) and the weaker the graph invariant (i.e., it's more easy to nd two non-isomorphic graphs for which the values of the invariant are the same) that we use to check at step 8 of the procedure Set the correspondence, the more alternatives for setting of φ we shall obtain in the course of its implementation, and it is more hard to nd among them such a bijection that is an isomorphism or to nd out that there is no isomorphism for input graphs. Conversely, the graphs with less regular structure, such as, e.g., random graphs, give GI instances that are easy to solve using known algorithms since they have automorphism groups of low cardinalities.
The following lemma shows that, solving GI for the graphs G and H, we may have alternative variants for setting isomorphism of the graphs only if we have such i 2 V (G) that jOi(G)j > 1.
Lemma 1. Let G ≃ H, i1; i2 2 V (H). i1 2 Oi2 (H) if and only if there exists a vertex j 2 V (G) and such isomorphisms φ1; φ2 : V (G) ! V (H) that φ1(j) = i1, φ2(j) = i2. Proof. Let i1 2 Oi2 (H). It follows that there is 2 Aut(G) such that (i1) = i2. Let φ1 be an isomorphism of G onto H and let j = φ1 1(i1), j 2 V (H). Let φ2 = ◦ φ1. We have φ2(j) = ( ◦ φ1)(j) = (i1) = i2 and φ2 is an isomorphism of G onto H. Conversely, suppose there are such i1; i2 2 V (H), j 2 V (G) and isomorphisms φ1, φ2 that φ1(j) = i1, φ2(j) = i2. Then = φ2 ◦φ1 1 2 Aut(H) and (j) = i2, i.e., i1 2 Oi2 (H).
In the course of the transformations (
Let us consider an example of the algorithm operating that illustrates this reasoning. Let G and H be the input graphs shown on a picture below.
Reduction of the number of variants to set φ is shown in table 1. After the 4-th
iteration, we have jAut(G(