Computational methods for determining graph invariants

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(m³). 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.