|
Article information
2016 , Volume 21, ¹ 6, p.71-88
Prolubnikov A.V.
Precision and complexity of the computations that are needed to solve the graphs isomoprhism problem by equality check of polynomials
Purpose. To show that graph modified characteristic n-variable polynomial may be used to obtain an algorithm to numerically solve the graph isomorphism problem in the general case. Methodology. We use methods of graph theory, linear algebra as well as numerical methods of linear algebra combined with the elements of group theory. Findings. We present an algorithm for the graph isomorphism problem and show that it may be implemented numerically. For graphs on n vertices, we prove that the equality checking the values of the graphs modified characteristic polynomials at the predefined points may be implemented in O(n 4 ) time, although such polynomial of n variables has 2n coefficients and this fact makes direct computations of the polynomial value impossible in some point with the required accuracy in polynomial time. We also prove that to do this checking we need machine numbers with O(n 2 ) mantissas length. It is shown that the algorithm may be seen as the process of the graphs modifications in the course of which we reduce cardinalities of automorphisms groups of the graphs that we obtained. Thus we reduce the time that is needed to solve the individual problems using presented backtracking scheme of the algorithm. We show that probability of a mistake for the algorithm is negligible if parameter of the algorithm is sufficiently large. Originality/value. The new complete graph invariant is considered and it is proved that it may be used to solve the graph isomorphism problem numerically.
[full text]
Keywords: graph isomorphism, complete invariant, computational complexity
Author(s):
Prolubnikov Alexander Vyacheslavovich
Associate Professor
Office: Omsk F.M. Dostoevsky State University
Address: 644077, Russia, Omsk, Mira avenue 55-a
Phone Office: (3812) 64-42-38
E-mail: a.v.prolubnikov@mail.ru
SPIN-code: 4729-9643 References:
[1] Filotti, I.S., Mayer, J.N. A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. Proceedings of the 12th Annual ACM Symposium on Theory of Computing. 1980. P. 236243. Doi:10.1145/800141.804671.
[2] Babai, L., Grigoryev, D.Yu., Mount, D.M. Isomorphism of graphs with bounded eigenvalue multiplicity. Proceedings of the 14th Annual ACM Symposium on Theory of Computing. 1982. P. 310324. DOI: 10.1145/800070.802206.
[3] Luks, E.M. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences. 1982; 25(1):4265.
[4] Ullman, J.R. An algorithm for subgraph isomorphism. Journal of the ACM. 1976; 23(1):3142.
[5] Schmidt, D.C., Druffel, L.E. A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices. Journal of the ACM. 1976; 23(3):433445.
[6] McKay, B.D. Practical graph isomorphism. 10th Manitoba Conference on Numerical Mathematics and Computing, Winnipeg, 1980. Congressus Numerantium. 1981; (30):4587.
[7] Foggia, P., Sansone, C., Vento, M. A performance comparison of five algorithms for graph isomorphism. Proceedings of the 3rd IAPR TC-15 International Workshop on Graph-based Representations in Pattern Recognition. Italy. 2001:188199.
[8] Prolubnikov, A.V. Reduction of the graph isomorphism problem to equality checking of polynomials of n-variables. Trudy Instituta Matematiki i Mekhaniki. Ekaterinburg: IMM of Ural Department of Russian Academy of Sciences; 2016; 22(1):235240. (In Russ.)
[9] Cvetkovic, D.M, Doob, M., Sachs, H. Spectra of Graphs. New York: Academic Press; 1980: 368.
[10] Seidel, J.J. Strongly regular graphs with (−1, 1, 0) adjacency matrix having eigenvalue 3. Linear Algebra and its Applications. 1968; (1):281298.
[11] Lipton, R.J., Vishnoi, N.K., Zalcstein, Z. A generalization of the characteristic polynomial of a graph. Georgia Institute of Technology, CC Technical Report, GIT-CC-03- 51, 2003. Available at: https://smartech.gatech.edu/bitstream/handle/1853/6511/GIT-CC-03- 51.pdf (accessed: 24.02.2016).
[12] Foggia, P., Sansone, C., Vento, M. A database of graphs for isomorphism and sub-graph isomorphism benchmarking. Proceedings of the 3rd IAPR TC-15 Intern. Workshop on Graphbased Representations, Italy. 2001: 157168.
[13] Strongly regular graphs on at most 64 vertices. Avaialble at: http://www.maths.gla.ac.uk/∼es/srgraphs.php (accessed: 24.02.2016).
[14] Schwartz, J. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM. 1980; 27(4):701717.
[15] Zippel, R. Probabilistic algorithms for sparse polynomials. International Symposium on Symbolic and Algebraic ManipulationProceedings, EUROSAM 79, Marseille, France, 1979. Lecture Notes in Computer Science . Springer Berlin Heidelberg: Springer-Verlag; 1979; (72):216226.
[16] Gantmacher, F.R. The theory of matrices. AMS Chelsea Publishing: Reprinted by American Mathematical Society; 2000: 660. ISBN 0821813765.
[17] Faizullin, R.T., Prolubnikov, A.V. An algorithm of the spectral splitting for the double permutation cipher. Pattern Recognition and Image Analysis. 2002; 12(4):365 375.
[18] Berezin, I.S., Zhidkov, N.P. Computing Methods. Vol. 2. Oxford: Pergamon Press; 1965: 678.
Bibliography link:
Prolubnikov A.V. Precision and complexity of the computations that are needed to solve the graphs isomoprhism problem by equality check of polynomials // Computational technologies. 2016. V. 21. ¹ 6. P. 71-88
|
