Graph Isomorphism
The Graph Isomorphism problem currently has a deterministic quasi-polynomial time algorithm. This time bound is a breakthrough from the previously best known upper bound of exponential time (in the size of the graph). I started looking at Babai’s paper on [1512.03547] Graph Isomorphism in Quasipolynomial Time (arxiv.org). Many of the key concepts involve abstract algebra, e.g. automorphism groups. This video is a great refresher on automorphisms.
I found it helpful to dig a little bit deeper into automorphisms via Visual Group Theory, Lecture 4.6: Automorphisms – YouTube. This video uses Cayley graphs, which I haven’t studied before but is still a good overview of the automorphism groups.
The “Graph Isomorphism in Quasipolynomial Time” paper is quite involved. I was pleasantly surprised to find a University of Chicago lecture by Babai on this result few months ago. I still came away short of understanding the proof after watching the video.
The foundations of this line of research comes partially from the paper showing that Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time. I started looking into this paper to try to understand the fundamentals in the simpler case where the degree of the graph is bounded. There are many algebraic concepts that I still need a refresher on to get an intuitive feel for this old paper. However, [2011.01366] Recent Advances on the Graph Isomorphism Problem (arxiv.org) gives a higher level view of what is happening and is therefore my key aide at this point in shedding some light on these graph isomorphism algorithms. It has, for example, pointed me to the color refinement algorithm. Details about this algorithm are available in this Color Refinement and its Applications paper.
Leave a Reply