Isomorphism and Similarity of Graphs

• Applicant: Professor Dr. Johannes Köbler
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 188403235

The graph isomorphism problem (GI) is one of the few remaining natural candidates for an NP-problem that is neither in P nor NP-complete. Efficient algorithms are only known for certain restrictions of GI, some of these could even be classified as complete for important subclasses of P. We want to extend these completeness results to less restrictive versions of GI.In many applications it is of interest how much two given graphs differ. So far, the usual approach was to use heuristics without analysing these from a theoretical point of view to a satisfying extent. We want to extend known isomorphism algorithms to compute a measure of similarity of non-isomorphic input graphs.Additionally, we want to further investigate the unrestricted GI, especially considering random distributions of input graphs that are close to the worst case. For the classical average case model there are already known algorithms that decide GI efficiently and correctly with high probability.

• DFG Programme: Research Grants