ARTÍCULO
TITULO

Computational methods for determining graph invariants

Sergey Kurapov    
Maxim Davidovsky    

Resumen

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.

 Artículos similares

       
 
Yu Chen, Jianwan Ding, Yu Chen and Dong Yan    
The introduction of a dynamic model in robot trajectory tracking control design can significantly improve its trajectory tracking accuracy, but there are many uncertainties in the robot dynamic model which can be dealt with through robust control and ada... ver más
Revista: Applied Sciences

 
Michiel van der Vlag, Lionel Kusch, Alain Destexhe, Viktor Jirsa, Sandra Diaz-Pier and Jennifer S. Goldman    
Global neural dynamics emerge from multi-scale brain structures, with nodes dynamically communicating to form transient ensembles that may represent neural information. Neural activity can be measured empirically at scales spanning proteins and subcellul... ver más
Revista: Applied Sciences

 
Wenbo Peng and Jinjie Huang    
Current object detection methods typically focus on addressing the distribution discrepancies between source and target domains. However, solely concentrating on this aspect may lead to overlooking the inherent limitations of the samples themselves. This... ver más
Revista: Applied Sciences

 
Yunfei Yang, Zhicheng Zhang, Jiapeng Zhao, Bin Zhang, Lei Zhang, Qi Hu and Jianglong Sun    
Resistance serves as a critical performance metric for ships. Swift and accurate resistance prediction can enhance ship design efficiency. Currently, methods for determining ship resistance encompass model tests, estimation techniques, and computational ... ver más

 
Giorgio Lazzarinetti, Riccardo Dondi, Sara Manzoni and Italo Zoppis    
Solving combinatorial problems on complex networks represents a primary issue which, on a large scale, requires the use of heuristics and approximate algorithms. Recently, neural methods have been proposed in this context to find feasible solutions for r... ver más
Revista: Algorithms