Algebraic Methods in the Study of Graph Isomorphism
Lead Research Organisation:
University of Cambridge
Department Name: Computer Science and Technology
Abstract
The aim of this project is to understand the complexity of the graph isomorphism problem.
We aim to understand the limitations of well known polynomial time algorithms which constitute an approximation to the problem. The Weisfeiler-Leman and invertible map tests are two well known ones. Whilst the former has been well studied, the latter has many related open questions. For instance, how does this test behave over finite fields?
Is this the best polynomial approximation of graph isomorphism? We would also like to relate this to known quantum graph invariants, such as the k-boson invariant and the quantum
isomorphism game. We conjecture that there is an extension of the latter which forms an invariant which is stronger than Weisfeiler-Leman.
Our project is based on previous work by Bjarki Holm, Anuj Dawar and Simone Severini. Most of this work was formulated in terms of logic and pebble games on graphs. We aim to formulate our ideas (as well as their previous work) in terms of algebras from graphs, permutation groups and combinatorics so as to make it more accessible to scientists from a more general background.
We aim to understand the limitations of well known polynomial time algorithms which constitute an approximation to the problem. The Weisfeiler-Leman and invertible map tests are two well known ones. Whilst the former has been well studied, the latter has many related open questions. For instance, how does this test behave over finite fields?
Is this the best polynomial approximation of graph isomorphism? We would also like to relate this to known quantum graph invariants, such as the k-boson invariant and the quantum
isomorphism game. We conjecture that there is an extension of the latter which forms an invariant which is stronger than Weisfeiler-Leman.
Our project is based on previous work by Bjarki Holm, Anuj Dawar and Simone Severini. Most of this work was formulated in terms of logic and pebble games on graphs. We aim to formulate our ideas (as well as their previous work) in terms of algebras from graphs, permutation groups and combinatorics so as to make it more accessible to scientists from a more general background.
Organisations
People |
ORCID iD |
| Anuj Dawar (Primary Supervisor) | |
| Danny Vagnozzi (Student) |
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N509620/1 | 01/10/2016 | 30/09/2022 | |||
| 2119781 | Studentship | EP/N509620/1 | 01/10/2018 | 30/09/2021 | Danny Vagnozzi |
| Description | We have determined a polynomial time algorithm for deciding equivalence between structures in logics with linear algebraic operators over any field. We also established relationships between the distinguishing power of linear algebraic logics and proof systems with algebraic rules over finite fields. |
| Exploitation Route | There are many open questions that we address. The main one, is whether the invertible map test over all fields provide a polynomial time algorithm for deciding graph isomorphism. |
| Sectors | Digital/Communication/Information Technologies (including Software),Education |