IJIRCST

Reducing Complexity of Graph Isomorphism Problem

Shalini Bhaskar Bajaj

Graph isomorphism has been discussed in the literature as NP-hard problem. It has applications in various areas. Work done earlier in this area employs backtracking for identifying isomorphism between given two graphs as a result with the increase in size of the graph the time to solve the problem becomes exponential. The proposed work presents a polynomial time algorithm (PTGI) which tries to solve graph isomorphism between given two directed graphs. Some distinguishing features associated with each vertex are stored. These features are exploited in dividing the vertices of the graph into equivalence classes from which canonical representation of the graph is generated. Comparing these features of the vertices of the given two graphs solves isomorphism in polynomial time.

Graph isomorphism, canonical representation, equivalence class, polynomial

[1] L. P.Cordella, P. Foggia, C. Sansone and M. Vento, An improved algorithm for matching large graphs, In Proc. of the 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, Ischia (Italy), (2001).

[2] T. Coreman, C. Leiserson and R. Rivest, Introduction to Algorithms, Cambridge, MA: MIT Press, 1990.

[3] J. Hopcroft and J. Wong, Linear Time Algorithm for Isomorphism of Planar Graphs, Proc. 6th Annual ACM Symp. Theory of Computing, (1974) 172-184.

[4] E.M. Luks, Isomorphism of Graphs of bounded valance can be tested in polynomial time, Journal of Computer System Science, (1982) 42-65.

[5] B. D. McKay, The nauty page, March 2004, http://cs.anu.edu.au/~bdm/nauty/

[6] B.D. McKay, Practical Graph Isomorphism, Congressus Numerantium, 30 (1981) 45-87.

[7] T. Miyazaki, The complexity of McKay’s canonical labeling algorithm, in Groups and Computation, II L. Finkelstein and W. M. Kantor, eds., Amer. Math. Soc., Providence, RI, (1997) 239-256.

[8] Jose Luis Lopez-Presa and Antino Fernandez, Graph Isomorphism Testing Without Full Authmorphism Group Computation, vol. 4 (2004), No. 3 (TR-GSYC-2004-3).

[9] D.C. Schmidt and L.E. Druffel, A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices, 23 (1976) 433-445.

[10] J.R. Ullman, An Algorithm for Subgraph Isomorphism, Journal of the Association for Computing Machinery, 23 (1976) 31-42.

[11] B. Weisfeiler and Lehman, On Construction and Identification of Graphs, Lecture Notes in Math, Springer, Berlin, 558 (1976).

[12] Jose Luis Lopez-Presa and Antonio Fernandez Anta. Fast Algorithm for Graph Isomorphism testing, In SEA, volume 5526 of LNCS, pages 221-232, 2009

[13]S. Auwatananmongkol. Inexact graph matching using a genetic algorithm for image recognition. Pattern Recognition Letters, 28912), pages 1428-1437, 2007

[14]D. Conte, P. Foggia and M. Vento. Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs. Journal of Graph Algorithms and Applications, 11(1), pages 99-143, 2007

[15] Fahad Bin Mortuza. A Polynomial Time Graph Isomorphism Algorithm for Graphs that are not locally Triangle-free, Cornell University Library, 2016

[16] Imelda Atastina, Benhard Sitohang, G.A.Putri Saptawati and Veronica S. Moertini. An implementation of graph mining to find evolution of communication data records. In the Proceedings of the 2018 Intl. Conf. on Data Science and InformationTechnology (DSIT ’18), Singapore, July 20-22, 2018, pp. 79-84, 2018

[17] Anand Padmanabha Iyer, Zaoxing Liu and Xin Jin, Shivaram Venkataraman, Vladimir Braverman and Ion Stoica, ASAP: Fast, Approximate Graph Pattern Mining at Scale, Open Access to the Proc. of the 13th USENIX Symp. On Operating System Design and Implementation, October 8-10, 2018, Carlsbad, CA, USA

[18] Vinicius Dias, Carlos H.C. Teixeira, Dorgival Guedes, Wanger Meira and Srinivasan Parthasarthy, Fractal: A General-Purpose Graph Pattern Mining System, In Proc. Of the 2019 Intl. Conf. on Management of Data (SIGMOD ’10), Amserdam, Netherlands, Jun 30- Jul 5, 2019, pp. 1357-1374

[19] Cheng Zhao, Zhibin Zhang, Peng Xu, Tianqi Zheng and Xueqi Cheng, Kaleido: An efficient out of core graph mining system on a single machine, Proc. Of the VLDB Endowment, vol. 11, no. 13, 2018, DOI: https://doi.org/TBD

[20] Fengcai Qiao, Xin Zhang, Pei Li, Zhao Y un Ding, Shanshan Jia and Hui Wang, A parallel approach for frequent subgraph mining in a single large graph using spark, Appl. Science, 2018, vol. 8, pp. 230, DOI: 10.3390/app8020230

[Shalini Bhaskar Bajaj (2020), Reducing Complexity of Graph Isomorphism Problem, International Journal of Innovative Research in Computer Science & Technology (IJIRCST), Vol-8, Issue-3, Page No-117-125], (ISSN 2347 - 5552). www.ijircst.org

Shalini Bhaskar Bajaj

Professor, Department of Computer Science and Engineering, Amity University Haryana, Gurugram, India (e-mail: shalinivimal@gamil.com)

DOI:

DOI: 10.21276/ijircst.2020.8.3.15 DOI URL: https://doi.org/10.21276/ijircst.2020.8.3.15

Copyright © 2021 by author(s) and International Journal of Innovative Research in Computer Science & Technology Journal. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (CC BY 4.0) (http://creativecommons.org/licenses/by/4.0)