Marking Vertices to Find Graph Isomorphism Mapping Based on Continuous-Time Quantum Walk

Area of Science:

• Graph Theory
• Quantum Computing
• Algorithm Design

Background:

• The graph isomorphism problem determines if two graphs are topologically identical.
• Existing quantum walk algorithms offer polynomial-time solutions but often fail to produce the isomorphism mapping.
• Current methods struggle with regular graphs due to their inherent symmetry.

Purpose of the Study:

• To develop an effective algorithm for discovering structure-preserving isomorphism mappings.
• To improve the performance of graph isomorphism algorithms, particularly on challenging regular graphs.
• To leverage quantum walks for enhanced topological structure sensitivity.

Main Methods:

• The IsoMarking algorithm utilizes quantum walks sensitive to topological structures.
• Vertices are marked to mitigate the impact of graph symmetry.
• A novel approach ascertains bijection consistency to obtain qualified mappings.

Main Results:

• IsoMarking effectively discovers isomorphism mappings.
• The algorithm demonstrates significantly improved performance on both ordinary and regular graphs.
• Experiments on 1585 graph pairs validate the algorithm's efficacy.

Conclusions:

• IsoMarking provides an effective solution to the graph isomorphism problem.
• The algorithm successfully addresses limitations of prior methods, especially for symmetric graphs.
• Quantum walks, enhanced by IsoMarking, offer a powerful tool for graph isomorphism detection.