Accelerations for Graph Isomorphism

2017/06/27 by Caishi Fang, Fang, Caishi
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1706.09230

openalex publication_date 2017/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we present two main results. First, by only one conjecture (Conjecture 2.9) for recognizing a vertex symmetric graph, which is the hardest task for our problem, we construct an algorithm for finding an isomorphism between two graphs in polynomial time O(n³) . Second, without that conjecture, we prove the algorithm to be of quasi-polynomial time O(n^{1.5log n}) . The conjectures in this paper are correct for all graphs of size no larger than 5 and all graphs we have encountered. At least the conjecture for determining if a graph is vertex symmetric is quite true intuitively. We are not able to prove them by hand, so we have planned to find possible counterexamples by a computer. We also introduce new concepts like collapse pattern and collapse tomography, which play important roles in our algorithms.

Related

• Recent Advances on the Graph Isomorphism Problem
• A polynomial time parallel algorithm for graph isomorphism using a quasipolynomial number of processors
• Graph isomorphisms in quasi-polynomial time
• Polynomial Time Algorithm for Graph Isomorphism Testing
• The direct algorithm for solving of the graph isomorphism problem