Logo Logo
Switch Language to German
Fink Amores, Michael Christian (25. March 2021): The Graph Isomorphism Problem and the GI-Completeness of Selected Problems from Context-Free Grammars and Rewrite Systems. Bachelor, Faculty of Mathematics, Computer Science and Statistics, Ludwig-Maximilians-Universität München.


Graph isomorphisms are adjacency and label (equivalence class) preserving one-to-one correspondences between vertex sets of possibly labelled graphs. The graph isomorphism problem is then the task of deciding whether two given graphs are isomorphic or not and basis of complexity class GI, containing all problems with polynomial reduction to former problem. We highlight history and state of the art research on graph isomorphism related problems, with special focus on categorisation of GI in the complexity hierarchy and its relation to the unsolved P = NP problem, where strong theoretic and heuristic evidence suggests that GI is NP-intermediate. The core of the thesis is study of GI-completeness of selected problems from context-free grammars and term rewriting systems. We show polynomial equivalence of the graph isomorphism problem and decision problems on context-free and regular grammars, involving grammar isomorphisms and isomorphic strict interpretations, describing bijective mappings between nonterminals and terminals of different symbol sets. Grammar concepts are specialised to term rewriting systems, formalising substitution based on a function/variable symbol term model. Isomorphism on such finite structures involve local, on a per rule basis, and global rewriting of respective symbol sets, including arbitrary combinations. Completely local term rewriting system isomorphism can be determined in polynomial time by introduction of local templates, subject to different restrictions. Explicit pseudocode algorithms are subsequently provided to support those claims. In contrast, different graph encodings are used to prove that global rewriting of atleast one symbol set already leads to GI-completeness of the related decision problem.