Abstract
In this paper we present a novel approach to the graph isomorphism problem. We combine a direct approach, that tries to find a mapping between the two input graphs using backtracking, with a (possibly partial) automorphism precomputing that allows to prune the search tree. We propose an algorithm, conauto, that has a space complexity of O(n 2 logn) bits. It runs in time O(n 5) with high probability if either one of the input graphs is a G(n,p) random graph, for p ∈ [ω(ln 4 n / n ln ln n ), 1 − ω(ln 4 n / n ln ln n )]. We compare the practical performance of conauto with other popular algorithms, with an extensive collection of problem instances. Our algorithm behaves consistently for directed, undirected, positive, and negative cases. Additionally, when it is slower than any of the other algorithms, it is only by a small factor.
Partially supported by grants MICINN TIN2008-06735-C02-01, CAM S-0505/TIC/0285, and MEC PR2008-0015.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arvind, V., Kurur, P.P.: Graph isomorphism is in SPP. In: FOCS 2002 (2002)
Babai, L., Kučera, L.: Canonical labeling of graphs in linear average time. In: FOCS 1979 (1979)
Babai, L., Luks, E.M.: Canonical labeling of graphs. In: STOC 1983 (1983)
Boppana, R., Hastad, J., Zachos, S.: Does co-NP have short interactive proofs? Information Processing Letters 25, 27–32 (1987)
Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: An improved algorithm for matching large graphs. In: Proc. of the 3rd IAPR-TC-15 Int’l Workshop on Graph-based Representations (2001)
Czajka, T., Pandurangan, G.: Improved random graph isomorphism. J. of Discrete Algorithms 6(1), 85–92 (2008)
Fortin, S.: The graph isomorphism problem. Technical Report TR 96-20, U. of Alberta, Edmonton, Alberta, Canada (July 1996)
Gati, G.: Further annotated bibliography on the isomorphism disease. J. of Graph Theory 3(2), 95–109 (2006)
Goldberg, M.: The graph isomorphism problem. In: Gross, J.L., Yellen, J. (eds.) Handbook of graph theory. Discrete Mathematics and its Applications, ch. 2.2, pp. 68–78. CRC Press, Boca Raton (2003)
Mathon, R.: A note on the graph isomorphism counting problem. Information Processing Letters 8(3), 131–132 (1979)
McKay, B.D.: Practical graph isomorphism. Congr. Numer. 30, 45–87 (1981)
McKay, B.D.: The nauty page. CS Dept., Australian National U. (2004), http://cs.anu.edu.au/~bdm/nauty/
Miyazaki, T.: The complexity of McKay’s canonical labeling algorithm. In: Finkelstein, L., Kantor, W.M. (eds.) Groups and Computation II. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 28 (1997)
López Presa, J.L.: Efficient Algorithms for Graph Isomorphism Testing. Ph.D thesis, ETSI Telecomunicación, U. Rey Juan Carlos, Madrid, Spain (March 2009), http://www.diatel.upm.es/jllopez/tesis/thesis.pdf
Read, R.C., Corneil, D.G.: The graph isomorphism disease. J. of Graph Theory 1, 339–363 (1977)
Schöning, U.: Graph isomorphism is in the low hierarchy. J. of Computer and System Sciences 37(3), 312–323 (1988)
Singler, J.: Graph isomorphism implementation in LEDA 5.1. Technical report, Algorithmic Solutions Software GmbH (December 2005)
Ullmann, J.R.: An algorithm for subgraph isomorphism. J. ACM 23(1) (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
López-Presa, J.L., Fernández Anta, A. (2009). Fast Algorithm for Graph Isomorphism Testing. In: Vahrenhold, J. (eds) Experimental Algorithms. SEA 2009. Lecture Notes in Computer Science, vol 5526. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02011-7_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-02011-7_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02010-0
Online ISBN: 978-3-642-02011-7
eBook Packages: Computer ScienceComputer Science (R0)