This week, we need to do work to address a component of our application that requires immediate attention. As a result, you may experience ERA to be intermittently available. We apologize for any inconvenience this may cause, and thank you for your patience as we attend to the care and feeding of ERA!
 199 views
 173 downloads
The Graph Isomorphism Problem

 Author(s) / Creator(s)

Technical report TR9620. The graph isomorphism problem can be easily stated: check to see if two graphs that look differently are actually the same. The problem occupies a rare position in the world of complexity theory, it is clearly in NP but is not known to be in P and it is not known to be NPcomplete. Many subdisciplines of mathematics, such as topology theory and group theory, can be brought to bear on the problem, and yet only for special classes of graphs have polynomialtime algorithms been discovered. Incongruently, this problem seems very easy in practice. It is almost always trivial to check two random graphs for isomorphism, and fast hardware implementations exist for application domains such as image processing. This paper is mostly a survey of related work in the graph isomorphism field. We examine the problem from many angles, mirroring the multifaceted nature of the literature. We survey complexity results for the graph isomorphism problem, and discuss some of the classes of graphs which have known polynomialtime algorithms. Many of these algorithms have constants that are so large as to negate their usefulness in actual applications. Thus a number of practical techniques, which do not have a polynomial worst case, are also examined. We end the paper by discussing some graphs which are ``hard'' for practical algorithms, and present experimental results which demonstrate a class of graphs on which practical algorithms run into difficulty.  TRIDID TR9620

 Date created
 1996

 Subjects / Keywords

 Type of Item
 Report

 License
 Attribution 3.0 International