Parallel Algorithm for Solving the Graph Isomorphism Problem
Vladimir Vasilyevich Vasilchikov · Automatic Control and Computer Sciences · 2021
Abstract— In this paper, we propose a parallel algorithm for solving the graph isomorphism problem. Our goal is to construct a suitable vertex substitution or to prove the absence of such. The problem is solved for undirected graphs without loops and multiple edges; it is assumed that the graphs can be disconnected. The question of the existence or absence of an algorithm with a polynomial complexity is currently open. Therefore, as for any time-consuming task, the question arises about speeding up its solution by parallelizing the algorithm. The RPM_ParLib library developed by the author allows developing effective applications for parallel computing on a local network under the control of the runtime environment .NET Framework. Supporting a recursive-parallel programming style, such applications have the ability to generate parallel branches of computation directly during program execution and dynamically redistribute work between computing modules. The library can be used for applications written in any programming language supported by the .NET Framework. To solve our problem and conduct a numerical experiment, several applications in the C# language were developed. The purpose of the experiment was to study the acceleration achieved due to the recursive-parallel organization of calculations. Specially generated random regular graphs with various degrees of vertices were used as the initial data. A detailed description of the algorithm and experiment, as well as the results obtained, are also given.