Graph isomorphism—Characterization and efficient algorithms

Abstract

The Graph isomorphism problem involves determining whether two graphs are isomorphic and the computational complexity required for this determination. In general, the problem is not known to be solvable in polynomial time, nor to be NP-complete. In this paper, by analyzing the algebraic properties of the adjacency matrices of the undirected graph, we first established the connection between graph isomorphism and matrix row and column interchanging operations. Then, we prove that for undirected graphs, the complexity in determining whether two graphs are isomorphic is at most $\mathcal{O}\left(n^{3}\right) $.

Keywords

Undirected graph / Characterization / Isomorphism / Algorithm / Polynomial time complexity

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgements

This work was supported in part by the U.S. National Science Foundation (CCF1919154 and ECCS-1923409).

References

[1] Graph discrete mathematics. [Online]. Available: https://en.wikipedia.org/wiki/Graph_(discrete_mathematics).

[2] Z. Blumenfeld, Graph machine learning: An overview - key concepts for getting started. [Online]. Available: https://towardsdatascience.com/graph-machine-learning-an-overview-c996e53fab90.

[3] M. Grohe, P. Schweitzer, The graph isomorphism problem, Commun. ACM 63 (11) (2020) 128-134, [Online]. Available: http://dx.doi.org/10.1145/3372123.

[4] B.D. McKay, A. Piperno, Practical graph isomorphism ii, J. Symbolic Comput. ( 2014) 94-112, [Online]. Available: http://dx.doi.org/10.1016/j.jsc.2013.09.003.

[5] Graph isomorphism problem. [Online]. Available: https://en.wikipedia.org/wiki/Graph_isomorphism_problem.

[6] R. Karp, Reducibilities among combinatorial problems, in: R. Miller, J. Thatcher (Eds.), Complexity of Computer Computations, Plenum Press, New York, 1972, pp. 85-103.

[7] M. Garey, D. Johnson, Computers and Intractability: A Guide To the Theory of NP-Completeness, Freeman, 1979.

[8] Principal component analysis part 1: The different formulations. [Online]. Available: https://towardsdatascience.com/principal-component-analysis-part-1-the-different-formulations-6508f63a5553.

[9] How are eigenvalues used in real life?.

[10] Applications of eigenvalues and eigenvectors. [Online]. Available: https://www.intmath.com/matrices-determinants/8-applications-eigenvalues-eigenvectors.php.

[11] Adjacency matrix. [Online]. Available: https://mathworld.wolfram.com/AdjacencyMatrix.html.

[12] D. Margalit, J. Rabinoff, Interactive linear algebra. [Online]. Available: https://textbooks.math.gatech.edu/ila/ila.pdf.