×

Improved random graph isomorphism. (English) Zbl 1157.05046

Summary: Canonical labeling of a graph consists of assigning a unique label to each vertex such that the labels are invariant under isomorphism. Such a labeling can be used to solve the graph isomorphism problem. We give a simple, linear time, high probability algorithm for the canonical labeling of a \(G(n,p)\) random graph for \[ p\in [\omega (\ln ^4n/n \ln\ln n), 1 - \omega (\ln^4n/n \ln\ln n)]. \] Our result covers a gap in the range of \(p\) in which no algorithm was known to work with high probability. Together with a previous result by Bollobás, the random graph isomorphism problem can be solved efficiently for \(p\in [\Theta (\ln n/n),1 - \Theta (\ln n/n)]\).

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Babai, L.; Erdős, P.; Selkow, S. M., Random graph isomorphism, SIAM J. Computing, 9, 3, 628-635 (1980) · Zbl 0454.05038
[4] Bollobás, B., Random Graphs (2001), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0979.05003
[6] Frieze, A.; McDiarmid, C., Algorithmic theory of random graphs, Random Structures and Algorithms, 10, 5-42 (1997) · Zbl 0868.05048
[7] Karp, R., Probabilistic analysis of a canonical numbering algorithm for graphs, (Proc. Symposia in Pure Math., vol. 34 (1979), American Mathematical Society: American Mathematical Society Providence, RI), 365-378
[8] Knuth, D., The Art of Programming: Sorting and Searching (1998), Addison-Wesley: Addison-Wesley Reading, MA
[10] Mitzenmacher, M.; Upfal, E., Probability and Computing: Randomized Algorithms and Probabilistic Analysis (2005), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1092.60001
[11] Motwani, R.; Raghavan, P., Randomized Algorithms (1995), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0849.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.