Computational methods for determining graph invariants

Sergey Kurapov, Maxim Davidovsky

Abstract


In general, a universal algorithm for testing a pair of graphs G and H for isomorphism exists. It is grounded on the fact that the rows and the corresponding columns of the adjacency matrix of the graph G can be rearranged until it turns into another, equal to the adjacency matrix of the graph H. Moreover, the maximum number of permutations (exhaustive search) is equal to n!. If isomorphism is not determined after n! permutations – the graphs are not isomorphic.

For most algorithmic problems in graph theory, it is possible to construct a polynomial algorithm or prove that the problem belongs to the class of NP-complete. The problem of determining graph isomorphism is one of the few classical problems in graph theory, for which neither one nor the other has been successfully implemented so far (although for some special classes of graphs researchers have managed to construct polynomial algorithms).

An important role in the problem of determining graph isomorphism is played by so-called invariants – some, usually numeric, values or an ordered set of values (hash function) that characterize the structure of the graph and do not depend on the graphical representation of the graph or the way the vertices are designated. An invariant is called complete if the coincidence of the graph invariants is necessary and sufficient to establish an isomorphism. The currently known complete invariants (for example, maxi code and mini code) are hard to compute and do not allow effectively solving the problem of determining graph isomorphism. In 2015, L. Babai announced an algorithm that allows solving the isomorphism problem in quasi-polynomial time; this algorithm was refined in 2017.

Thus, many attempts to construct computational algorithms based on the use of the adjacency matrix A(G) for determining the complete invariant of the graph G have not led to the desired result so far. On this way, a wide variety of heuristics for determining isomorphism have been developed, usually focused on certain types of graphs.

In this paper, we consider the results of constructing a complete invariant of the graph G based on the edge-cut spectrum matrix WS(G). The computational complexity of the algorithm for constructing the matrix WS(G) is O(m3). In order to experimentally evaluate the proposed computational method for determining the complete invariant of the graph G, the authors developed a proof-of-concept software implementation and carried out a number of computational experiments for various types of graphs.


Full Text:

PDF (Russian)

References


A. A. Zykov, Theory of Finite Graphs, 1969.

W. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich. Lectures on graph theory. M.: Science, 1990.

A. V. Pogrebnoy and V. K. Pogrebnoy, “Method of graph vertices differentiation and solution of the isomorphism problem”, Bulletin of Tomsk Polytechnic University, vol. 326, iss. 6, 2015, pp. 34–45.

G. M. Khitrov, “On the diversity of the graph and the application of this concept to the problem of graph isomorphism”, Vestn. St. Petersburg un., Ser. 10: Applied Mathematics, Computer Science, Control Processes, vol. 2., 2006, pp. 91–100.

A. A. Zykov. Fundamentals of graph theory. BCS Associates, 1990.

B. D. McKay and A. Piperno, “Practical Graph Isomorphism”, J. Symbolic Computation, vol. 60, 2014, pp. 94–112.

S. Datta, N. Limaye, P. Nimbhorkar, T. Thierauf, and F. Wagner, “Planar Graph Isomorphism is in Log-Space”, in 24th Annual IEEE Conference on Computational Complexity, Paris, 15–18 Jul. 2009, pp. 203–214.

S. A. Lindell, “Logspace Algorithm for Tree Canonization”, in Proc. of the 24th Annual ACM Symposium on the Theory of Computing, New York, 1992, pp. 400–404.

S. V. Prolubnikov, “On a new complete invariant of acyclic graphs”, PDM, №3, 2010.

M. N. S. Swami and K. Thulasiraman. Graphs, Networks and Algorithms. Wiley, 1980.

F. Harary. Graph Theory. Reading, MA.: Addison-Wesley, 1969.

S. V. Kurapov, M. V. Davidovsky, and A. V. Nelasaya. Graph isomorphism, Zaporizhzhya, ZNU, 2019.

S. V. Kurapov and M. V. Davidovsky, “Graph edge cut and the graph isomorphism problem”, Visnyk of Zaporizhzhya National University. Physical and Mathematical Sciences, № 1, Zaporizhzhya: ZNU, 2017, pp. 222–234.


Refbacks

  • There are currently no refbacks.


Abava  Absolutech Convergent 2020

ISSN: 2307-8162