An Improved Heuristic Algorithm for the Graph Isomorphism Problem

Document Type : Original Article

Authors

Software Systems Research and Development Laboratory / Faculty of Computer Engineering, Shahid Rajaee Teacher Training University

Abstract

The Graph Isomorphism Problem (GIP) is an open problem because of its computational complexity. No polynomial-time deterministic algorithm has been proposed yet, and heuristic and meta-heuristic approaches have been the only ways to solve it. Because its belonging to the NP-complete problem has not yet been proven, it is considered an NP problem. This paper introduces a simple but efficient polynomial algorithm, both in terms of computational complexity and memory complexity, to determine the isomorphism of connected unlabeled graphs. The proposed algorithm introduces two functions that compute the features for all vertices and edges. The outputs of the function provide canonical labeling to the given graphs, and a comparison of these labels specifies the graph isomorphism of the given graphs. The experimental results show that the proposed algorithm correctly detects the isomorphism of the graphs in more than 99% of cases. The algorithm requires Ο(n^3) time where n is the number of vertices of the given graphs.

Keywords

References

[1] Rafiee, P. Moradi, A. Ghaderzadeh, “A swarm intelligence based multi-label feature selection method hybridized with a local search strategy”, Tabriz Journal of Electrical Engineering, vol. 51, no. 4, pp. 443-454, 2021.
[2] Mokhtarizadeh, B. Zamani Dehkordi, M. Mosleh, Ali Barati, “Influence Maximization using Time Delay based Harmonic Centrality in Social Networks”, Tabriz Journal of Electrical Engineering, vol. 51, no. 3, pp. 359-370, 2021.
[3] K. Wong, “Model matching in robot vision by subgraph isomorphism”, Pattern Recognition, vol. 25, no. 3, pp. 287-304, 1992.
[4] Kandel, H. Bunke, M. Last, “Applied Graph Theory in Computer Vision and Pattern Recognition”, Berlin, Springer, 2007.
[5] A. Abdulrahim, M. Misra, “A graph isomorphism algorithm for object recognition”, Pattern Analysis and Applications, vol. 1, no. 3, pp. 189-201, 1998.
[6] Washio, H. Motoda, “State of the art of graph-based data mining”, ACM SIGKDD Explorations Newsletter, vol. 5, no. 1, pp. 59-68, 2003.
[7] Conte, P. Foggia, C. Sansone, M. Vento, “Graph matching applications in pattern recognition and image processing”, In IEEE International Conference on Image Processing, September 2003, Barcelona, Spain, pp. 21-24.
[8] Wasserman, K. Faust, “Social Network Analysis: Methods and Applications”, Cambridge University Press, 1994.
[9] Sanfeliua, R. Alquézarb, J. Andradea, J. Climentc, F. Serratosad, J. Vergésa, “Graph-based representations and techniques for image processing and image analysis”, Pattern Recognition, vol. 35, no. 3, pp. 639-650, 2002.
[10] H. Rouvray, A.T. Balaban, “Chemical applications of graph theory”, Academic Press London, 1979.
[11] Aittokallio, B. Schwikowski, “Graph–based methods for analysing networks in cell biology”, Briefings in Bioinformatics, vol. 7, no. 3, pp. 243-255, 2006.
[12] Valiente, “Algorithms on Trees and Graphs”, Springer-Verlag, 2002.
[13] Babai, E.M. Luks, “Canonical labeling of graphs”, In 15th Annual ACM Symposium on Theory of Computing, December 1983, New York, United States, pp. 171–183.
[14] Babai, P. Erdos, M. Selkow, “Random graph isomorphism”, SIAM Journal on Computing, vol. 9, no. 3, pp. 628-635, 1980.
[15] Babai, L. Kucera, “Canonical labeling of graphs in linear average time”, In 20th IEEE Symposium on Foundations of Computer Science, October 1979, San Juan, USA, pp. 39-46.
[16] Babai, “Graph isomorphism in quasi-polynomial time”, In 48th Annual ACM Symposium on Theory of Computing, June 2016, New York, United States, pp. 684-697.
[17] D. McKay, A. Piperno, “Practical graph isomorphism II”, Journal of Symbolic Computation, vol. 60, pp. 94-112, 2014.
[18] Miyazaki, “The complexity of McKay’s canonical labeling algorithm”, Groups and Computation, vol. 28, no. 2, pp. 239-256, 1996.
[19] M. Karp, “Reducibility Among Combinatorial Problems”, In Symposium on the Complexity of Computer Computations, March 1972, Yorktown Heights, New York, pp. 85-103.
[20] V. Aho, J.E. Hopcroft, J.D. Ullman, “The Design and Analysis of Computer Algorithms”, Addison-Wesley, 1974.
[21] E. Hopcroft, J.K. Wong, “Linear time algorithm for isomorphism of planar graphs”, In 6th Annual ACM Symposium on Theory of Computing, April 1974, Washington, USA, pp. 172-184.
[22] D. McKay, A. Piperno, "Nauty Traces", Available: http://pallini.di.uniroma1.it.
[23] Nourollah, S. Check, “A Heuristic Algorithm for Graph Isomorphism Problem Based on Eccentricity”, Computing Sciences and Information Technologies, vol. 17, no. 2, pp. 45-51, 2019 (in Persian).
[24] C. Freeman, “A set of measures of centrality based on betweenness”, Sociometry, vol. 40, no. 1, pp. 35-41, 1977.
[25] ANU College of Engineering & Computer Science. "collections of non-isomorphic graphs," Available: http://users.cecs.anu.edu.au/~bdm/data/graphs.html.
[26] Database of interesting graphs. "The House of Graphs," Available: https://hog.grinvin.org.
[27] Generate graphs. "Generate all unlabeled simple graphs on a given number of vertices," Available: http://combos.org/nauty.
[28] Regular Graphs Page. "Connected regular graphs," Available: http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html.
[29] P. Cordella, P. Foggia, C. Sansone, M. Vento, “An improved algorithm for matching large graphs”, In Proceedings of the 3rd IAPR-TC-15 International Workshop on Graph-based Representations, May 2001, Ischia, Italy, pp. 149-159.

Files

Share

How to cite

Statistics