Professor Kunsoo Park of SNU Department of Computer Science and Engineering Develops the World's Highest Performance Algorithm for Graph Isomorphism Problems

Professor Kunsoo Park's research team of the SNU College of Engineering Department of Computer Science and Engineering has developed the world's highest performance graph isomorphism algorithm technology. The graph isomorphism problem refers to the issue that arises when determining whether two graphs are isomorphic, and is a key problem that is addressed for the process of graphical analysis in various fields of application such as social network services, bioinformatics and chemical informatics. In 1979, Garey & Johnson introduced 12 unsolved problems regarding the ambiguity of whether they belonged to NP-complete or P, among which graph isomorphism is a particularly well-known problem that remains unsolved even till 40 years later of today.
When considering practicality, for the past 30 years, nauty/Traces has been known to be the fastest algorithm to solve graph isomorphism problems. Professor Kunsoo Park's team developed the world's best-performing algorithm that solves graph isomorphism problems quickly in real data and showed that the developed algorithms solve problems thousands of times faster on average than nauty/Traces on benchmark graph data.
The developed graph isomorphism algorithm was distributed as an open SW and the students Geonmo Gu and Yehyun Nam of Professor Kunsoo Park's research lab won the gold prize regarding their work at 'The 2020 Open SW Developer Conference' hosted by the Ministry of Science and ICT.
The results of Professor Kunsoo Park's research on graph isomorphism algorithms have been accepted by ICDE 2021 and is to be announced at the ICDE 2021 in April 2021.
 
G. Gu, Y. Nam, K. Park, Z. Galil, G.F. Italiano, and W.-S. Han, Scalable Graph Isomorphism: Combining Pairwise Color Refinement and Backtracking via Compressed Candidate Space, International Conference on Data Engineering (ICDE) 2021.