The Graph Isomorphism Problem and the GI-Completeness of Selected Problems from Context-Free Grammars and Rewrite Systems

Fink Amores, Michael Christian (25. März 2021): The Graph Isomorphism Problem and the GI-Completeness of Selected Problems from Context-Free Grammars and Rewrite Systems. Bachelorarbeit, Fakultät für Mathematik, Informatik und Statistik, Ludwig-Maximilians-Universität München.

Abstract

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.

• Dokumententyp: LMU München: Studienabschlussarbeit
• Keywords: Graph Isomorphism; Term Rewriting Systems; Formal Languages; GI-Completeness; Templates; Normal Forms
• Fakultät: Mathematik, Informatik und Statistik > Informatik > Ausgewählte Abschlussarbeiten
• Themengebiete: 000 Informatik, Informationswissenschaft, allgemeine Werke > 004 Informatik ; 500 Naturwissenschaften und Mathematik > 510 Mathematik
• Sprache: Englisch

Literaturliste

A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Co., Boston, Massachusetts, USA, first edition, 1974

J. Avenhaus. Reduktionssysteme – Rechnen und Schliessen in gleichungsdefinierten Strukturen. Springer-Lehrbuch. Springer, Berlin, Heidelberg, D, first edition, 1995

L. Babai. Trading Group Theory for Randomness. In Proceedings of the Sev- enteenth Annual ACM Symposium on Theory of Computing, STOC ’85, pages 421–429, New York, NY, USA, 1985. Association for Computing Machinery

L. Babai. Graph Isomorphism in Quasipolynomial Time. https://arxiv.org/pdf/1512.03547.pdf [2016-01-19], 2016

L. Babai. Fixing the UPCC case of Split-or-Johnson. https://people.cs.uchicago.edu/~laci/upcc-fix.pdf [2017-01-14], 2017

L. Babai. GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMOR- PHISM PROBLEM, pages 3319–3336. World Scientific Publishing Co Pte Ltd, 2019

K. S. Booth and C. J. Colbourn. Problems polynomially equivalent to graph isomorphism. Technical Report CS-77-04, University of Waterloo, 1979

L. Babai and P. Codenotti. Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. In 2008 Fourty-Ninth Annual IEEE Symposium on Foundations of Computer Science, pages 667–676, Washington, DC, USA, 2008. IEEE Computer Society

L. Babai and E. M. Luks. Canonical Labeling of Graphs. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC ’83, pages 171–183, New York, NY, USA, 1983. Association for Computing Machinery

H. L. Bodlaender. Polynomial algorithms for graph isomorphism and chro- matic index on partial k-trees. Journal of Algorithms, 11(4):631–643, 1990

JY. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389–410, 1992

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, Cambridge, Massachusetts, USA, third edition, 2009

C. J. Colbourn. On testing isomorphism of permutation graphs. Networks, 11(1):13–21, 1981

S. A. Cook. The Complexity of Theorem-Proving Procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC ’71, pages 151–158, New York, NY, USA, 1971. Association for Computing Machinery

S. A. Cook. A Hierarchy for Nondeterministic Time Complexity. In Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, STOC ’72, pages 187–192, New York, NY, USA, 1972. Association for Computing Machinery

R. Frucht. Herstellung von Graphen mit vorgegebener abstrakter Gruppe. Compositio Mathematica, 6(1):239–250, 1939

J. Gentzen. A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata. Post on Blog gentzen.wordpress.com, 2015. Accessed: 2021-03-10

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman and Company, New York, NY, USA, first edition, 1979

H. A. Helfgott, J. Bajpai, and D. Dona. Graph isomorphisms in quasi- polynomial time. https://arxiv.org/pdf/1710.04574.pdf [2017-10-12], 2017

T. Hertli, R. A. Moser, and D. Scheder. Improving PPSZ for 3-SAT using Critical Variables. https://arxiv.org/pdf/1009.4830.pdf [2018-10-31], 2011

J. Hartmanis and R. E. Stearns. On the Computational Complexity of Algorithms. Transactions of the American Mathematical Society, 117(1):285–306, 1965

J. E. Hopcroft and J. K. Wong. Linear Time Algorithm for Isomorphism of Planar Graphs (Preliminary Report). In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC ’74, pages 172–184, New York, NY, USA, 1974. Association for Computing Machinery

R. Impagliazzo and R. Paturi. Complexity of k-SAT. In Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat.No.99CB36317), pages 237–240, Washington, DC, USA, 1999. IEEE Computer Society

R. M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer US, 1972

E. Klarreich. Landmark Algorithm Breaks 30-Year Impasse. Online Article published by Quanta Magazine, 2015. Accessed: 2021-03-12

K. Kutzkov and D. Scheder. Using CSP To Improve Deterministic 3-SAT. https://arxiv.org/pdf/1007.1166.pdf [2018-10-26], 2010

R. E. Ladner. On the Structure of Polynomial Time Reducibility. J. ACM, 22(1):155–171, 1975

E. M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, 25(1):42–65, 1982

D. J. Rosenkrantz and H. B. Hunt. Testing for Grammatical Coverings. Theoretical Computer Science, 38(1):323–341, 1985

U. Schöning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences, 37(3):312–323, 1988

U. Schöning. Theoretische Informatik – kurz gefasst. Spektrum Akademischer Verlag, Heidelberg, D, fifth edition, 2008

P. Schweitzer. Problems of Unknown Complexity: Graph isomorphism and Ramsey theoretic numbers. PhD thesis, Naturwissenschaftlich-Technische Fakultäten der Universiät des Saarlandes, 2009

D. A. Spielman. Faster Isomorphism Testing of Strongly Regular Graphs. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, pages 576–584, New York, NY, USA, 1996. Association for Computing Machinery

M. Schmidt-Schauß, C. Rau, and D. Sabel. Algorithms for Extended Alpha- Equivalence and Complexity. In Femke van Raamsdonk, editor, 24th International Conference on Rewriting Techniques and Applications (RTA 2013), volume 21 of Leibniz International Proceedings in Informatics (LIPIcs), pages 255–270, Dagstuhl, D, 2013. Schloss Dagstuhl-Leibniz-Zentrum für Informatik

L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3(1):1–22, 1976

D. van Melkebeek. Randomness and Completeness in Computational Com- plexity. Springer-Verlag, Berlin, Heidelberg, D, first edition, 1950

V. N. Zemlyachenko, N. M. Korneenko, and R. I. Tyshkevich. Graph isomor- phism problem. Journal of Soviet Mathematics, 29(4):1426–1481, 1985