Reducing Complexity of Graph Isomorphism Problem

Authors

  • Shalini Bhaskar Bajaj Professor, Department of Computer Science and Engineering, Amity University Haryana, Gurugram, India Author

Keywords:

Graph isomorphism, canonical representation, equivalence class, polynomial

Abstract

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.  

Downloads

Download data is not yet available.

References

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).

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.

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

Downloads

Published

2020-05-05

Issue

Vol. 8 No. 3 (2020): International Journal of Innovative Research in Computer Science and Technology (May) 2020

Section

Articles

How to Cite

Reducing Complexity of Graph Isomorphism Problem . (2020). International Journal of Innovative Research in Computer Science & Technology, 8(3), 117–125. Retrieved from https://acspublisher.com/journals/index.php/ijircst/article/view/13279