UNIV. NEWS. NORTH-CAUCAS. REG. TECHNICAL SCIENCES SERIES. 2022; 1: 21-30
http://dx.doi.org/10.17213/1560-3644-2022-1-21-30
STUDY ON THE EFFICIENCY OF INVARIANTS USED FOR TESTING GRAPH ISOMORPHISM
Ivanchenko Aleхandеr N. – Candidate of Technical Sciences, Professor, Department «Computer Software», ian2008.52@mail.ru
Ivanchenko Kirill N. – Graduate Student, kni2012.15@gmail.com
Shaida Alexey Yu. – Graduate Student, Department «Computer Software», alexsey_@mail.ru
Abstract
The article discusses the effectiveness of the practical application of various invariants used to check graphs for isomorphism. These invariants are described and classified in previous publications of the authors. A technique for the numerical study of the effectiveness of invariants is proposed in terms of such criteria as the cost of computer time for performing the necessary calculations and the ability of an invariant to distinguish non-isomorphic graphs, expressed as the proportion of correctly recognized non-isomorphic graphs among a given set. The implementation of this technique in the form of a software package is described, which makes it possible to carry out numerical experiments on reference sets of non-isomorphic graphs obtained using the well-known NAUTY program library. The results of computational experiments using this complex are presented. By means of a comparative analysis, the ranking of invariants by efficiency was carried out and it was shown that “heavy” invariants, which require a lot of computer time, have the greatest distinguishing ability. At the same time, the distinguishing power of quickly calculated (“light”) invariants is not great. The idea of reducing the time spent on processing large sets of graphs is practically demonstrated by first splitting the initial set into equivalence classes using "light" invariants and then applying "heavy" invariants to each class.
Keywords: graph isomorphism problem, graph invariant, resistive distance, multiset, equivalence class, object-oriented programming
Full text: [in elibrary.ru]
References
- Ivanchenko A.N., Ivanchenko K.N. Analysis of invariants used for graph isomorphism testing and the principles of their systematization. University News. North Caucasian Region. Technical Sciences=Bulletin of Higher Educational Institutions. North Caucasus Region. Technical Sciences. 2021; (4): 17-23. http://dx.doi.org/10.17213/1560-3644-2021-4-17-23/ (In Russ.).
- Petrovskij A.B. Spaces of sets and multisets. Moscow: Editorial URSS; 2003. 248 p.
- Cormen Thomas H., Leiserson Charles E., Rivest Ronald L., Clifford Stein. Algorithms: construction and analysis, 3rd. Moscow: «Williams»; 2013. 1328 p.
- Knuth D.E. The Art of Computer Programming. Vol. 3. Sorting and Searching. Moscow: «Williams»; 2007. 824 p.
- Equivalence class. Available at: <https://en.wikipedia.org/wiki/Equivalence_class> (accessed 15.02.2022).
- Programming languages – C++. International Standard ISO/IEC 14882:2020(E).
- McKay B.D., Piperno A. Nauty and Traces. Software distribution web page. Available at: <http://users.cecs.anu.edu.au/~bdm/nauty/> (accessed 15.02.2022).
- McKay B.D. Practical Graph Isomorphism. Congressus Numerantium, 30 (1981). Рp. 45-87. Available at: <http://users.cecs.anu.edu.au/~bdm/nauty/pgi.pdf> (accessed 15.02.2022).
- McKay B. D., Piperno A. Practical Graph Isomorphism, II. J. Symbolic Computation (2013), vol. 60, p. 94-112. Available at: <https://arxiv.org/pdf/1301.1493.pdf> (accessed 15.02.2022).
- Emelichev V.A., Melnikov O.I., Sarvanov V.I., Tyshkevich R.I. Lectures on graph theory. Moscow, Nauka, 1990. 384 p.
- Ivanchenko A.N. About the choice of data structures for solving problems on graphs. Research results-2019: materials of the IV National Conference of Faculty and Researchers, Novocherkassk, May 14, 2019. Platov South-Russian State Polytechnic University (NPI). – Рp.79-81. (In Russ.).
- Ivanchenko A.N, Ivanchenko K.N. Graph isomorphism criterion based on resistance distance. University News. North Caucasian Region. Technical Sciences Series=Bulletin of Higher Educational Institutions. North Caucasus Region. Technical Sciences. 2020; (2): 13-18. (In Russ.).
- Ivanchenko A.N., Ivanchenko K.N. Using multisets to implement vector invariants of graphs. Research results-2021: materials of the VI National Conference of Faculty and Researchers.Novocherkassk: SRSPU (NPI); 2021. Рp. 7-10.
- Basic concepts of the chrono library (C++). Available at: <https://habr.com/ru/post/324984/> (accessed 15.02.2022).