=Paper=
{{Paper
|id=Vol-1623/paperco14
|storemode=property
|title=Reduction of the Graph Isomorphism Problem to Equality Checking of n-variables Polynomials and the Algorithms that Use the Reduction
|pdfUrl=https://ceur-ws.org/Vol-1623/paperco14.pdf
|volume=Vol-1623
|authors=Alexander Prolubnikov
|dblpUrl=https://dblp.org/rec/conf/door/Prolubnikov16
}}
==Reduction of the Graph Isomorphism Problem to Equality Checking of n-variables Polynomials and the Algorithms that Use the Reduction==
https://ceur-ws.org/Vol-1623/paperco14.pdf
Reduction of the Graph Isomorphism Problem
to Equality Checking of n-variables Polynomials
and the Algorithms that use the Reduction
Alexander Prolubnikov
Omsk State University, Omsk, Russian Federation
a.v.prolubnikov@mail.ru
Abstract. The graph isomorphism problem is considered. We assign modified
characteristic polynomials for graphs and reduce the graph isomorphism prob-
lem to the following one. It is required to find 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 specified points without direct evaluation of
the values. We give justification 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.
Keywords: graph isomorphism, complete invariant, computational complexity
1 The graph isomorphism problem
In the graph isomorphism problem (GI), we have two simple graphs G and H. Let
V (G) and V (H) denote the sets of vertices of the graphs and let E(G) and E(H)
denote the sets of their edges. V (G) = V (H) = [n]. An isomorphism of the graphs G
and H is a bijection φ : V (G) → V (H) such that for all i, j ∈ V (G)
(i, j) ∈ E(G) ⇔ (φ(i), φ(j)) ∈ V (H).
If such a bijection exists, then the graphs G and H are isomorphic (we shall denote it
as G ≃ H), else the graphs are not isomorphic. In the problem, it is required to present
the bijection that is an isomorphism or we must show non-existence of such a bijection.
We may state GI using adjacency matrices of graphs. Let (A)ij denote the ij-th
element of a matrix A. The adjacency matrix of a graph G is a matrix A(G) which has
dimension of n×n. Elements of this matrix are defined as follows:
{
1, if (i, j) ∈ E(G),
(A(G))ij =
0, else.
Let A(G) and A(H) be adjacency matrices of the graphs G and H. Then
G ≃ H ⇔ ∃φ ∈ 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
Reduction of the Graph Isomorphism Problem 97
where Sn is a symmetric group on [n] and
{
1, if i = φ(j),
(Pφ )ij =
0, else.
By this formulation of the problem, the two graphs are isomorphic if and only if we
can obtain adjacency matrix of the first 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 numer-
ous applications where it arises. For example, without solving GI, we cannot practically
solve the following problem. In the problem we need to find an n-vertices graph that
has some specified 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 first 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 first 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 isomor-
phisms, 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 classification of
98 A. Prolubnikov
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 non-
isomorphic 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) = max {(A)π(1) ||(A)π(2) || . . . ||(A)π(n) },
π∈Sn
where “||” denotes concatenation of bit strings and (A)i denotes the i-th row of the
adjacency matrix A(G). For some classes of graphs, canonical codes may be computed in
polynomial time [1], [10]. Every complete invariant gives a way for graph canonization.
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 field of characteristic q, where q is a prime number or zero.
In our work, we assign modified characteristic polynomials for graphs and reduce the
graph isomorphism problem to the following one. It is required to find out, is there such
an enumeration of the graphs vertices that the modified characteristic polynomials of
the graphs are equal. The modified 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 justification of the algorithms and give the scheme of its numerical real-
ization. The example of the approach implementation and the results of computational
experiments are presented.
2 The modified characteristic polynomial of a graph
Let us consider the characteristic polynomial of a graph and some of its modifications
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 ∈ V (G).
Reduction of the Graph Isomorphism Problem 99
Some modifications of the characteristic polynomial are considered in [13]. The
examples are the graph Laplacian L(G) that is defined as
L(G) = D(G) − A(G),
the signless graph Laplacian |L(G)| that is defined as
|L(G)| = D(G) + A(G),
and some other modifications which may be generalized by the polynomial ξG (x, y):
ξG (x, y) = det(xE − (A(G) − yD(G))).
Seidel polynomial [14] is another modification of the characteristic polynomial that
is obtained by modification 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 modifications of the characteristic polynomial is a
complete graph invariant.
The modified 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 ∈ V (G). Let x1 , . . . , xn be inde-
pendent variables and let X = diag(x1 , . . . , xn ).
Definition 1. For a graph G, |V (G)| = n, ηG (x1 , . . . , xn ) is a polynomial of the form
ηG (x1 , . . . , xn ) = det(A(G) + X). (1)
For graphs on n = 1, 2, 3 vertices, the polynomials of the form (1) are the following
ones:
1) n = 1: x1 ;
2) n = 2: x1 x2 , x1 x2 − 1;
3) n = 3: x1 x2 x3 , x1 x2 x3 − x1 , x1 x2 x3 − x1 − x3 , x1 x2 x3 − x1 − x2 − x3 + 2.
It is clear that we have different polynomials for non-isomorphi graphs no matter what
enumeration of its vertices we use for n = 1, 2, 3. ∏
For a subset c of V (G), let xc be a product of the form i∈c 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
i∈c xi in the polynomial ηG (x1 , . . . , xn ). Having c and φ ∈ Sn , let φ(c) be the image
of c: φ(c) = {φ(i) | i ∈ c}. For x = (x1 , . . . , xn ), xφ = (xφ(1) , . . . , xφ(n) ). The following
theorem holds.
100 A. Prolubnikov
Theorem 1. G ≃ H and φ : V (G) → V (H) is an isomorphism of the graphs if and only
if
ηG (x1 , . . . , xn ) = ηH (xφ(1) , . . . , xφ(n) ). (2)
for all x ∈ Rn .
The polynomials ηG and ηH are equal if the coefficient of xc is equal to the coefficient
of xφ(c) for every subset c of V (G). Thus, the equality (2) holds if and only if A(G)c =
A(H)φ(c) for all subsets c of V (G). Let us prove the Theorem 1.
Proof. If G ≃ H and φ is an isomorphism of the graphs, then (2) holds since
A(H) = Pφ A(G)Pφ⊤ , (3)
and the coefficients of ηG and ηH , corresponded by φ, are equal to each other.
Let us show that if the equality (2) holds, then G ≃ H and φ is an isomorphism of
the graphs. Let us denote A(G) as A = (aij ) and B(G) as B = (bij ).
If (2) holds, then the coefficient of xc is equal to the coefficient of xφ(c) for all
subsets c of V (G). Thus, if we take c such that c = V (G) \ {i, j} for( some ) pair
0 aij
of vertices i, j ∈ V (G), we have Ac = Bφ(c) . This is equivalent to det =
aij 0
( )
0 bφ(i)φ(j)
det . So aij = bφ(i)φ(j) and (i, j) ∈ E(G) if and only if (φ(i), φ(j)) ∈
bφ(i)φ(j) 0
V (H), i.e., G ≃ H and φ is an isomorphism of the graphs.
Remark 1. To check the equality (2) for some φ, it suffice to check equality of the
coefficients that correspond to c such that |c| = n− 2. Since if Ac = Bφ(c) for such c,
then A(H) may be obtained from A(G) by permutation of its rows and columns. And,
since the equality (3) holds, then Ac = Bφ(c) for all subsets c of V (G).
3 The algorithms for GI that check equality of the values of
the modified characteristic polynomials at the specified
points
To check wether the two given graphs G and H are isomorphic, we try to find φ such
that the equality (2) holds. If such φ exists, then the graphs are isomorphic, else they
are not isomorphic.
The equality checking of coefficients of two polynomials of the form (1) may be
performed as it is presented in [12]. But if we check equality of the polynomials this
way, we need exponential time since ηG (x1 , . . . , xn ) has 2n coefficients. Such algorithm
has an exponential complexity no matter what instance of GI it solves. The algorithms
we present below solve GI by comparing of the values that the modified characteristic
polynomials take on the specified points of Rn . This approach make possible to signif-
icantly reduce the time that is needed to solve GI instance checking equality of the
modified characteristic polynomials of graphs. We present two heuristic algorithms to
implement the approach: the Direct algorithm for GI and its recursive modification.
Reduction of the Graph Isomorphism Problem 101
3.1 The Direct algorithm for GI
Let N ∈ N, S = {k/10N | 0 < k < 10N , k ∈ Z+ }, 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) +εi ei , i = 1, . . . , n. I.e., ε(1) = (ε1 , 0, . . . , 0), ε(2) = (ε1 , ε2 , . . . , 0),
. . ., ε(n) = (ε1 , ε2 , . . . , εn ).
In the course of implemetation of the algorithms we present below, we trying to set
(i)
a bijection φ : V (G) → V (H) such that ηG (ε(i) ) = ηH (εφ ). On the i-th iteration of the
Direct algorithm, we searching for such j ∈ V (H) that
ηG (ε(i) ) = ηH (ε(i−1)
φ + εi ej ). (4)
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 isomor-
phism, 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 first 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 ∈ S;
(i−1)
4 if (∃j ∈ J : ηG (ε(i) ) = ηH (εφ + εi ej ))
5 φ(i) ← j;
6 J ← J \{j};
7 else print ”G ̸≃ H”.
8 print ”G ≃ H, φ is an isomorphism of G and H”.
3.2 Recursive modification of the Direct algorithm for GI
Algorithm 2 we present below is a recursive modification 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).
102 A. Prolubnikov
Set the correspondence (i ∈ V (G))
1 if i = n
2 f lag ← true;
3 φ(n) ← k, where k such that J = {k};
4 exit.
5 else
6 for j ← 1 to n
7 choose at random εi ∈ S;
(i−1)
8 if (j ∈ J and ηG (ε(i) ) = ηH (εφ +εi ej ))
9 φ(i) ← j;
10 J ← J \{j};
11 Set the correspondence (i + 1);
12 if f lag = f alse
13 J ← J ∪{j};
14 φ(i) is not defined;
15 exit.
Algorithm 3 (G, H)
1 J ← V (H);
2 f lag ← f alse;
3 ∀i ∈ V (G) : φ(i) is not defined.
4 Set the correspondence(1);
5 if f lag
6 print ”G ≃ H, φ is an isomorphism of G and H”;
7 else
8 print ”G ̸≃ H”.
The recursive procedure Set the correspondence gets on input i ∈ V (G) and
set φ(i) ← j for j ∈ J ⊆ V (H) such that (4) holds. If there is no such j ∈ J, then we
modify the correspondence that was already setted up for i−1: we use the next element
of J for setting φ(i−1).
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 ∈ F [x1 , . . . , xn ] be a non-zero polynomial of total degree d ≥ 0
over a field F . Let S be a finite subset of F and let ε1 , . . . , εn be selected at random
independently and uniformly from S. Then
d
P[f (ε1 , . . . , εn ) = 0] ≤ .
|S|
If we have set up φ for every i = 1, . . . , n, then ηG (ε1 , . . . , εn ) = ηH (εφ(1) , . . . , εφ(n) ).
Let
f (ε1 , . . . , εn ) = ηG (ε1 , . . . , εn ) − ηH (εφ(1) , . . . , εφ(n) ).
Reduction of the Graph Isomorphism Problem 103
Total degree d of the polynomial f is equal to n, and F = R in this case. So, implement-
ing Algorithm 1 or Algorithm 2, if we obtain a message that G ≃ H and φ is an
isomorphism of the graphs, we have ηG ̸= ηH with the probability P[mistake] ≤ n/10N .
If we set N = n, then P[mistake] ≤ 1/10n−lg n and the message is correct with probabil-
ity no less than 1−1/10n−lg n . For the Direct algorithm, the message that the graphs are
not isomorphic may be incorrect. The message is always correct for its recursive modi-
fication since in this case there is no such φ that (4) holds successively for i = 1, . . . , n.
By the Theorem 1, it follows that the graphs are not isomorphic.
4 The numerical realization of the algorithms
and their computational complexity
Modifications of adjacency matrices. Let d be the maximum degree of vertices of G and
H: d = max{d1 , . . . , dn } (we suppose that G and H have the same degree sequences).
Let A and B be modified graph adjacency matrices of the following form
A := A(G) + 2dE, B := A(H) + 2dE. (5)
A(H) = Pφ A(G)Pφ⊤ for some bijection φ if and only if A = Pφ BPφ⊤ . If d > 0, then A
and B have the strong diagonal predominance:
∑
n
(A)ii = 2d ≥ 2di > di = (A)ij ,
j=1
j̸=i
so
∑
n
(A)ii − (A)ij > 0,
j=1
j̸=i
i = 1, n. Thus, the matrices of the form (5) satisfy the Hadamard conditions, and we
have det A ̸= 0, det B ̸= 0 [20]. For numerical realization of the algorithms that we have
presented, we use modified characteristic polynomials of the following form:
ηG (x1 , . . . , xn ) = det(A + X), ηH (xφ(1) , . . . , xφ(n) ) = det(B + Xφ ), (6)
where Xφ = Pφ XPφ⊤ . This modification is equivalent to the change of variables: xi →
xi + 2d.
We may consider the presented algorithms as a try to perform series of consistent
modifications of the matrices A and B:
A(i) := A(i−1) + εi Ei , B (i) := B (i−1) + εi Ej , (7)
where A(0) = A, B (0) = B, i = 1, . . . , n. We call the modifications of the form (7)
consistent, if we successively choose, for every i ∈ V (G), such j ∈ V (H) that holds
(i)
A{i} (B (i−1) + εi Ej ){j}
((A(i) )−1 )ii = = = ((B (i−1) + εi Ej )−1 )jj , (8)
det A(i) det(B (i−1) + εi Ej )
104 A. Prolubnikov
where Ei is n × n-matrix such that all of its elements are zeros except the i-th diagonal
element, which is equal to 1. It follows from (8) that
ηG (ε(i) ) = ηH (ε(i−1)
φ + ε i ej ) (9)
since the equality (8) is equivalent to the equality
(i−1)
ηG\{i} (ε(i) ) ηH \{j} (εφ + εi ej )
(i)
= (i−1)
. (10)
ηG (ε ) ηH (εφ + εi ej )
(i−1)
And, since the values ηG\{i} (ε(i) ) and ηH \{j} (εφ +εi ej ) not change when the value of
εi is changing, if the equality (10) holds for εi = 0 and for some non-zero value of εi , then
the equality (9) holds too. Thus, if we can perform series of consistent modifications for
i = 1, . . . , n, then the values of the polynomials of the graphs are equal at the specified
points ε(i) . As a result, we solve GI by using series of consistent modifications of graphs
adjacency matrices. This idea belongs to R.T. Faizullin. It was presented in [21].
Accuracy of computations and computational complexity. We compute the values of
((A(i) )−1 )ii by solving the system of linear equations A(i) y = ei . The value of ((A(i) )−1 )ii
is the i-th component of y. In order to solve the systems of linear equations, we may
use such iterative methods as the Gauss-Seidel method or the simple iteration method.
These methods converge at the rate of geometric progression for any starting vector
because the systems matrices have the diagonal predominance. Using the standard
numeric type double, we can solve instances of GI that was mentioned above choosing
εi ∈ [δ, 1), δ ≥ 0.001. The computational complexity of the Direct algorithm is equal to
O(n4 k), where k is a number of iterations of the method we use to solve the systems
of linear equations. In our computational experiments, we choosed k = 10. Recursive
modification of the Direct algorithm is exponential in the worst case.
5 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 ∈ 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
(i)
polynomials values in predefined points ε(i) and εφ . 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).
Reduction of the Graph Isomorphism Problem 105
Definition 2. The graph G automorphism group is a set of isomorphisms of the graphs
onto itself, i.e.,
Aut(G) = {ψ ∈ Sn | aij = aψ(i)ψ(j) , i, j = 1, n}.
Definition 3. The orbit of the vertex i ∈ V (G) is the set
Oi (G) = {ψ(i) | ψ ∈ Aut(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 modified 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 find 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 find among them
such a bijection that is an isomorphism or to find 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 ∈ V (G)
that |Oi (G)| > 1.
Lemma 1. Let G ≃ H, i1 , i2 ∈ V (H). i1 ∈ Oi2 (H) if and only if there exists a vertex
j ∈ V (G) and such isomorphisms φ1 , φ2 : V (G) → V (H) that φ1 (j) = i1 , φ2 (j) = i2 .
Proof. Let i1 ∈ Oi2 (H). It follows that there is ψ ∈ Aut(G) such that ψ(i1 ) = i2 . Let φ1
be an isomorphism of G onto H and let j = φ−1 1 (i1 ), j ∈ 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 ∈ V (H), j ∈ V (G) and isomorphisms φ1 , φ2 that φ1 (j) = i1 ,
φ2 (j) = i2 . Then ψ = φ2 ◦φ−1
1 ∈ Aut(H) and ψ(j) = i2 , i.e., i1 ∈ Oi2 (H).
In the course of the transformations (7), we subsequently obtain the graphs with
less regular structure than the input graphs have. The matrices A(i) and B (i) in (7)
may be considered as adjacency matrices of the graphs G(i) and H (i) . These graphs
has weighted loops, i.e., edges of the form (j, j) ∈ E(G). After the i-th iteration of the
algorithm, we have ψ(i) ̸= j for all ψ ∈ Aut(G(i) ) since the i-th and the j-th diagonal
elements of A(G(i) ) are not equal to each other with probability that negligibly close to
1 for all j ∈ V (G), i ̸= j. So we have |Oi (G(i) )| = 1. And, in accordance with the Lemma
above, we have no more than one way to set the value of φ(i) on the i-th iteration of
the algorithm. Performing transformations (7) and selecting unique values of the loops
weights εi , we subsequently obtain such G(i) and H (i) that
|Oj (G(i) )| = 1, j ≤ i, |Aut(G(i+1) )| ≤ |Aut(G(i−1) )|,
106 A. Prolubnikov
|Oφ(j) (H (i) )| = 1, j ≤ i, |Aut(H (i) )| ≤ |Aut(H (i−1) )|
and finally we get
|Oj (G(t) )| = |Oφ(j) (H (t) )| = 1, j = 1, n, |Aut(G(t) )| = |Aut(H (t) )| = 1
for t ≤ n−1.
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.
1q 3q
@A A@
A@ A@
A @ A @
2q
q3 4Aq @q5 6q q 5 2Aq @q1
@ A @ A
@ A @ A
@A @A
@Aq @Aq
6 4
Reduction of the number of variants to set φ is shown in table 1. After the 4-th
iteration, we have |Aut(G(4) )| = 1. In the table 2, the values of ((A(i) )−1 )jj are shown.
For all i = 1, n, if the value of φ(i) is setted up, then the multisets {((B (i) )−1 )jj }nj=1 and
{((A(i) )−1 )jj }nj=1 are equal. To compute these values, we perform 10 iterations of the
Gauss-Seidel method in order to solve the systems of equations of the form A(i) y = ei .
The initial approximation that we use is y (0) = (1, . . . , 1).
Table 1. Reduction of the alternative variants of setting φ for G and H.
Variants of setting φ
i |Aut(G(i) )|
1 2 3 4 5 6
0 3, 4 1, 2, 5, 6 1, 2, 5, 6 1, 2, 5, 6 1, 2, 5, 6 3, 4 16
1 3 1, 2, 5, 6 1, 2, 5, 6 1, 2, 5, 6 1, 2, 5, 6 4 8
2 3 1 2 5, 6 5, 6 4 2
3 3 1 2 5, 6 5, 6 4 2
4 3 1 2 5 6 4 1
6 Conclusions
In our work, we assign modified characteristic polynomials for graphs and reduce the
graph isomorphism problem to the following one. It is required to find out, is there such
an enumeration of the graphs vertices that the modified characteristic polynomials of
Reduction of the Graph Isomorphism Problem 107
Table 2. Computed values of ((A(i) )−1 )jj , i = 1, 3.
i εi ((A(i) )−1 )11 ((A(i) )−1 )22 ((A(i) )−1 )33 ((A(i) )−1 )44 ((A(i) )−1 )55 ((A(i) )−1 )66
0 0 0.078 0.094 0.094 0.094 0.094 0.078
1 0.861 0.070 0.095 0.095 0.095 0.095 0.078
2 0.672 0.070 0.087 0.095 0.095 0.095 0.079
3 0.372 0.071 0.087 0.091 0.094 0.094 0.079
4 0.475 0.072 0.087 0.091 0.089 0.095 0.080
the graphs are equal. The modified characteristic polynomial of a graph on n vertices
is a polynomial of n variables. We prove that two graphs are isomorphic if and only
if there is exists an enumeration of the graphs vertices such that the polynomials
of the graphs are equal. We present algorithms for the graph isomorphism problem
that use the redution. The algorithms check equality of the graphs polynomials values
at specified points without direct evaluation of the values. We give justification 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.
References
1. Lindell, S.: A logspace algorithm for tree canonization. Proc. of the 24th Annual ACM
Symposium on the Theory of Computing. 400–404 (1992)
2. Filotti, I.S., Mayer, J.N.: A polynomial-time algorithm for determining the isomorphism of
graphs of fixed genus. Proc. of the 12th Annual ACM Symposium on Theory of Computing.
236–243 (1980)
3. Babai, L., Grigoryev, D.Yu., Mount, D.M.: Isomorphism of graphs with bounded eigenvalue
multiplicity. Proc. of the 14-th Annual ACM Symposium on Theory of Computing. 310-324
(1982)
4. Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time.
Journal of Computer and System Sciences. 25. 42-65 (1982)
5. Ullman, J.R.: An algorithm for subgraph isomorphism. Journal of the ACM. 23. 31–42
(1976)
6. Schmidt, D.C., Druffel, L.E.: A fast backtracking algorithm to test directed graphs for
isomorphism using distance matrices. Journal of the ACM. 23(3). 433–445 (1978)
7. McKay, B.D.: Practical graph isomorphism. Congr. Numer. 30. 45–87 (1981)
8. Babai, L.: Graph Isomorphism in Quasipolynomial Time.
https://arxiv.org/abs/1512.03547
9. Cai, J-Y., Fürer, M., Immerman, N.: An optimal lower bound on the number of variables
for graph identification. Combinatorica. 12 (4). 389–410 (1992)
10. Datta, S., Limaye, N., Nimbhorkar, P., Thierauf, T., Wagner, F.: Planar graph isomor-
phism is in log-space. 24th Annual IEEE Conference on Computational Complexity. Paris,
France. 203–214 (2009)
11. Grigoriev, D.Yu.: Two Reductions of graph isomorphism problem for polynomials. J.
Soviet Math. 20. 2296–2298 (1982) (in Russian)
12. Prolubnikov, A.V.: Reduction of the graph isomorphism problem to equality checking of
polynomials of n-variables. Trudy Instituta Matematiki i Mekhaniki, Ekaterinburg: IMM
of Ural Department of Russian Academy of Sciences. 22(1). 235–240 (2016) (In Russ.)
108 A. Prolubnikov
13. Cvetkovic, D.M, Doob, M., Sachs, H.: Spectra of Graphs. Academic Press, New York
(1980)
14. Seidel, J.J.: Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3.
Lin. Alg. Appl. 1(2). 281–298 (1968)
15. Lipton, R.J., Vishnoi, N.K., Zalcstein, Z.: A generalization of the charac-
teristic polynomial of a graph. CC Technical Report, GIT-CC-03-51. 2003.
https://smartech.gatech.edu/bitstream/handle/1853/6511/GIT-CC-03-51.pdf
16. Foggia, P., Sansone, C., Vento, M.: A database of graphs for isomorphism and sub-graph
isomorphism benchmarking. Proc. of the 3rd IAPR TC-15 international workshop on graph-
based representations. 157–168 (2001)
17. Strongly regular graphs on at most 64 vertices. http://www.maths.gla.ac.uk/
∼es/srgraphs.php
18. Schwartz, J.: Fast probabilistic algorithms for verification of polynomial identities. Journal
of the ACM. 27. 701–717 (1980)
19. Zippel, R.: Probabilistic algorithms for sparse polynomials. Proc. of the International
Symposium on Symbolic and Algebraic Computation. 216–226 (1979)
20. Gantmaher, F.R.: Teoria matriz. Moskva: Izd-vo Nauka (1967) (in Russian)
21. Faizullin, R.T., Prolubnikov, A.V.: An algorithm of the spectral splitting for the double
permutation cipher. Pattern Recognition and Image Analysis. 12(4). 365–375 (2002)