Reducing Complexity of Graph Isomorphism Problem
Keywords:
Graph isomorphism, canonical representation, equivalence class, polynomialAbstract
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
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
