Graph Isomorphism Problem: Algorithms, Applications, and Solutions

This report delves into the graph isomorphism problem, a fundamental concept in computer science and artificial intelligence. It begins with a clear definition of graphs and graph isomorphism, differentiating between automorphism and isomorphism, and then explores various algorithmic approaches to solve this problem. The report covers trivial algorithms, applications using vertex degrees, and the use of canonical forms for graph comparison, including the computation methods. It also touches upon the application of graph isomorphism in Object-Oriented Petri Nets (OOPNs). The report highlights the complexity of the problem, categorizing it as NP-intermediate, and discusses the efficiency of different methods. The conclusion summarizes the key findings, emphasizing the significance of graph isomorphism in various applications and research areas. The report concludes with a discussion of normal forms and their relation to canonical forms.

Running head: GRAPH ISOMORPHISM PROBLEM
GRAPH ISOMORPHISM PROBLEM
Name of the Student
Name of the University
Course Code

1GRAPH ISOMORPHISM PROBLEM
Abstract:
The problem of graph isomorphism is simpler for defining and for understanding.
Many easily describable algorithms are there for solving these types of problems, however,
the time complexity associated with this type of problems is massively large. Hence,
minimizing the time complexity or increasing the efficiency of graph isomorphism problems
such that it can be practically implemented within a finite frame of time. Generally, these
problems do not solvable in polynomial time or falls in the category of NP complete and
hence often they are categorized in the type class NP-intermediate. The graph isomorphism
problem does not become NP complete until the hierarchy of polynomial time do not goes to
second level. This is one of the special case of subgraph-isomorphism which is about finding
whether a graph A which has a subgraph, is isomorphic to another graph B when it is known
that graph B is NP-complete. Different types of isomorphism problems are described in this
report and its different solution methods are described below.

2GRAPH ISOMORPHISM PROBLEM
Table of Contents
Introduction:.............................................................................................................................3
The graph Isomorphism problem:.........................................................................................3
Definition of graph:..............................................................................................................3
Defining graph isomorphism:..............................................................................................3
Relation between automorphism and isomorphism:.........................................................3
Algorithm overview for trivial graph isomorphism:............................................................3
Application by the graph vertices’ degrees:..........................................................................4
Application through canonical form of graphs:....................................................................4
Canonical form and its computation method:...................................................................4
Conclusion:...............................................................................................................................5
References:................................................................................................................................6

3GRAPH ISOMORPHISM PROBLEM
Introduction:
The problem of graph isomorphism can be seen in many applications like transport
planning, mathematics, computer science, engineering and many numerical fields. Many
structures or circuits can be represented by graphs and most of the time the requirement is to
know whether two or more structures gives the same representation from certain points of
views. Hence, two or more graphs are said to be isomorphic if the same number of vertices
are connected by same number of edges (Awang et al.). In other words two graphs are
isomorphic iff the other graph is a permutation of vertices and edges such that same number
of edges are present between two vertices.
As the isomorphism of graph arises in many situations, hence many methods to solve such
problems have been discussed. However, for the limitation of paper length a few methods are
discussed. For the practical implementation of comparatively huge sized graphs, usually the
canonical forms of graphs are used with appropriate algorithms. This bigger sized graphs
arises in particularly in the field of OOPNs (Object-oriented Petri nets). Towards the end of
this paper the isomorphism problem is described with the OOPNs.
The graph Isomorphism problem:
Definition of graph:
The concept of graph can be defined as a tuple G = (V, E), where V = set of all
vertices and E = set of all edges and E is a subset or equal set of (V 2) ∪ (VC2) ∪ V.
Here, V^2 = V X V = {(u , v) | u ∈ V, v ∈ V} is the all possible permutations of oriented
edges for all the set of vertices V. The given set of (VC2) = {{u , v}|u ≠ v, u ∈ V, v ∈ V} is

4GRAPH ISOMORPHISM PROBLEM
the permutations of non-oriented edges without the loops and the set V is the permutations of
non-oriented loops.
Defining graph isomorphism:
Two graphs are said to be mutually isomorphic if graph A = (VA , EA) and graph B =
(VB , EB) have some 1-to-1 mapping φ: VA → VB such that for all u and v ∈ VA : for all (u,v)
∈ EA ↔ (φ(u), φ(v)) ∈ EB, for all u,v ∈ EA ↔ {φ(u), φ(v)} ∈ EB and for all u ∈ VA : u ∈ EA
↔ φ(u) ∈ EB (Babai).
Relation between automorphism and isomorphism:
The graph automorphism is defined by the isomorphism between the Graph A and
Graph A itself, where graph A has some different permutation of edges (Horbez et al. 171-
187). Also, in this case it is bound to exist at least a single automorphism for every graph
which is also known as identical mapping (Jung 119).
Algorithm overview for trivial graph isomorphism:
For a simplistic approach only the oriented graphs are considered here. All the
oriented loops are allowed in the oriented graphs. The other modified graphs like non-
oriented or loop-less graphs are not considered here. Now, from the definition of the graph
isomorphism, all of the vertices are labelled in the form of 1,2,…n where n is the last of all
vertices. Now, if the lengths of this numbering sequence are different then the graphs cannot
be said as isomorphic (Zick et al. 11168). All the permutations of one sequence is checked to
ensure adjacency is maintained throughout. If the adjacency condition is maintained for a
limited number of permutations of graphs then those graphs are said to be mutually
isomorphic.

5GRAPH ISOMORPHISM PROBLEM
This particular approach is also known as the brutal force solution as every permutation has
been tested without the help of any additional information and the number steps required to
solve the problem increases exponentially with every addition of node in the graphs or in
other words if graph size becomes slightly large. The above method also known as back
tracking method is very much useful for the implementation of this algorithm.
Application by the graph vertices’ degrees:
The types of edges can be differentiated from the point of view of vertex in case of
the oriented graphs by their inward and outward edges. Loops are taken at a time as both
inward and outward edges (Deo). The total of inward edges are represented as ‘deg i’ and the
total of outward edges are represented as ‘deg o’ for all of the vertices of the graph G =
(V,E).
For all x ∈ V : deg i(x) = abs((u,x)u ∈ V, (u,x) ∈ E), deg o(x) = abs((x,u)u ∈ V, (x,u) ∈ E)
The individual total of ‘deg i’ and ‘deg o’ must be equals with the total number of vertices in
graph G. Hence, ∑ ¿¿.
In this particular method the vertices having the same degrees are permuted for preserving the
vertex adjacency. In most of the cases this particular algorithm is much more efficient than
the trivial algorithm. However, in few complicated cases there is a time complexity while
using this particular algorithm. For practical purposes the graph isomorphism is not applied
when the graphs have different sequence of degrees. At first in both graphs the degrees of all
the vertices are calculated. In the next step the order of vertices by degrees for the both
graphs is calculated. Now, if it found that the sequence orders of the degrees are different
then it can be concluded that the two graphs are not mutually isomorphic.

6GRAPH ISOMORPHISM PROBLEM
Application through canonical form of graphs:
In this approach the canonical form of two graphs are calculated first and if those are
found to be the same then those two graphs are mutually isomorphic elsewhere, it is
concluded that they are not mutually isomorphic. Now, if the matching of two or more graphs
are found then it becomes conclusive and with canonical form the matching can be found
within very less time than the previous method (Brinkmann 1437-1444). However,
sometimes computing the canonical form of some complex and large graphs can be as
difficult as forming the isomorphism algorithm.
Canonical form and its computation method:
A graph G with V vertices and E number of edges where V(G) = {1,2,…n} and the
matrix adjacency given by A(G) = (aij)i,j=1,…n and the characteristic vector is given by α(G) =
(a11 , a12 ,… , a1n , a21 , … , a2 n , … , ann). Also, a lexicographic order has been determined for each
of the characteristic vectors. Therefore, among the total set of characteristic vectors the
updated characteristic vector in lexicographic order corresponds to the canonical form of
graph G. Permutation of the order of vertices gives many of the characteristics vectors from a
single graph (Chein et al.). Now, assuming that Pn is the complete set of all possible
permutations with n number of elements, then it can be said that
Canonical(G)= α(Gp )p ∈Pn
max
Now, for the computation of canonical form at first all possible permutations of the graph G
is generated (Akutsu et al.). Although this approach do not enhance or increase the precision
of the solution as compared to the trivial graph isomorphism, but it takes less time for
computation. Now, time less or the method is efficient when the lexicographic order of
permutations are tested instead of testing all the permutations of vertices. Hence, a search tree
is formed where the permutations of vertices are represented by the branches of tree and the

7GRAPH ISOMORPHISM PROBLEM
node level position for the corresponding permutation is denoted by the distance between the
root and the current node. Hence, the tree generation allows to prune some of the branches
and hence increases the efficiency of the particular approach.
Now, the search tree can be constructed by the following method. It starts off with an empty
search tree. In the first level there exists node for all the vertices. Then the characteristics
vectors corresponding to its node at that level formed and the most recent node/s are selected
in lexicographic order (Fritz). Now, the nodes in the next level is generated extrapolating the
current selected nodes which are not used in higher level corresponding to the appropriate
branch. Now, the iteration continues and the tree generation stops when the number of level
gets equal to the number of vertices on a specific level. Hence, the canonical form becomes
the characteristic vector for the most updated level given in the lexicographic order.
This method is the most efficient for most of the graphs that has some reasonable size.
However, in case of some special types of graph like the full-connected graph the complexity
of reducing the canonical form becomes as complex as the trivial solution method and only a
few number of branches (or even none) can be pruned.
Conclusion:
Hence, in conclusion it can be stated that in the following paper the graph
isomorphism problem has been defined appropriately and methods for solving the problem
for different types of graphs has been determined. The proofs of different methods used are
beyond the scope of this paper and hence some articles by different authors about the proofs
has been cited in the references section. There are various other approaches to solve the graph
isomorphism problem and one of those is using the normal form. The normal form is very
much similar to the canonical form and the only difference is that when the normal forms of
two graphs are not same then there is some probability that two graphs are not isomorphic.

8GRAPH ISOMORPHISM PROBLEM
Like the canonical form method when the normal forms are same then it is absolutely certain
that the two graphs are isomorphic. Normal forms are faster to compute than the canonical
forms but absolute certainty of non-isomorphism can’t be guaranteed when the normal forms
are found to be different (Chein et al.). The graph isomorphism mainly arises at the time of
generation of abstract state space models known as Object Oriented Petri Nets (OOPN)
which is still being researched by many researchers. In state space models the states are
integrated iff the current state space is not equal to the new state space after renaming all the
states. The transformation of state space model to graph can be done by representing the
states as the nodes and the references for state transitions as the edges between them. The
graph isomorphism approach is simpler than solving a problem through state space
generation and hence it is applied in most scientists and researchers.

9GRAPH ISOMORPHISM PROBLEM
References:
Akutsu, Tatsuya, Colin de la Higuera, and Takeyuki Tamura. "A Simple Linear-Time
Algorithm for Computing the Centroid and Canonical Form of a Plane Graph and Its
Applications." LIPIcs-Leibniz International Proceedings in Informatics. Vol. 105. Schloss
Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
Awang, J., M. Pfeiffer, and Nikola Ruskuc. "Finite presentability and isomorphism of Cayley
graphs of monoids." arXiv preprint arXiv:1602.08502 (2016).
Babai, László. "Groups, Graphs, Algorithms: The Graph Isomorphism Problem." Proc.
Internat. Congr. of Mathematicians 2018 (2018).
Brinkmann, Gunnar. "Computing the maximal canonical form for trees in polynomial time."
Journal of Mathematical Chemistry 56.5 (2018): 1437-1444.
Chein, Michel, and Marie-Laure Mugnier. "Conceptual graphs are also graphs." International
Conference on Conceptual Structures. Springer, Cham, 2014.
Deo, Narsingh. Graph theory with applications to engineering and computer science. Courier
Dover Publications, 2017.
Fritz, Eric. "Maintaining Canonical Form After Edge Deletion." Proceedings of the 13th
Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages,
Programs and Systems. ACM, 2018.
Horbez, Camille, and Richard D. Wade. "Automorphisms of graphs of cyclic splittings of
free groups." Geometriae Dedicata 178.1 (2015): 171-187.
Jung, H. A. "automorphisms of graphs." Directions in Infinite Graph Theory and
Combinatorics: With an introduction by C. St. JA Nash-Williams 3 (2016): 119.

10GRAPH ISOMORPHISM PROBLEM
Zick, Kenneth M., Omar Shehab, and Matthew French. "Experimental quantum annealing:
case study involving the graph isomorphism problem." Scientific Reports 5 (2015): 11168.