Graph Isomorphism and Constraint Satisfaction Problems

Overview: The study of Computational Complexity is a vibrant area of research in Theoretical Computer Science and its central questions of "which problems in can be solved efficiently by computers?" and "what type of algorithms provide these solutions?" have a long history within Computer Science as a whole. Progress in answering these big questions is often limited to the analysis of specific classes of problems or specific algorithms and it can be difficult to relate results for one class of problem to those of another. However, recent work by Abramsky, Dawar (the supervisor of this project) and Wang introduced a surprising category theoretic construction linking two such classes of problems, namely Graph Isomorphism (GI) and Constraint Satisfaction Problems (CSP). This construction, known as the k-pebbling comonad, is as yet not very well understood but represents a promising new avenue for applying category theoretic methods to complexity theory. Thus the current project is aiming firstly to deepen our understanding of the k-pebbling comonad and secondly to find new more general constructions which will build further links between GI and CSP. Our intention is to create constructions which will (similar to the application of category theory in pure mathematics and elsewhere) unlock new connections between different classes of problems and suggest generalisations of existing results.

Concrete aims:

This project aims to increase our understanding of the links made by existing co-monadic constructions and to create similar new constructions. This will help us to better understand the recent developments in GI and CSP and the potential links between these areas. The questions which we will focus on initially involve generalising the existing constructions and include the following:
- Can we define a natural category for which homomorphism corresponds to the polynomial-time cases of Bulatov's algorithm for CSP in the same way that the pebbling co-monad captures local consistency? From this definition, what algorithms for isomorphism can we extract, and on what classes of graphs do they work?
- In the other direction, we know that the notion of isomorphism defined by the pebbling co-monad corresponds to the well-known idea of Weisfeiler-Lehman equivalence, can we construct a natural category where the notion of isomorphism corresponds to strictly stronger forms of equivalence such as IM-equivalence? What approximation to homomorphism does this yield? And, how do these relate to algorithms for CSPs?
- Can we relate the notions of isomorphism in these categories to the tractable cases of Babai's algorithm for GI? Do the hard (quasipolynomial) cases have a natural interpretation in these frameworks? To what do these hard cases correpond in terms of homomorphisms in these categories and can this be related to CSP?

Conclusion:

With these questions as a starting point, it is clear that this course of research has both achievable milestones and potential for exciting discoveries. At a minimum, this programme should lead to a better understanding of the commonalities between methods in CSP and GI. Further to this, the research could be considered a success if it led to the development of a general algebraic/categorical framework for the transfer of methods between GI and CSP. However the scope of this research would not be limited by this goal and researching such methods could conceivably lead to the discovery of general categorical transfer mechanisms between classes of problems or even, as alluded to in the conclusion of Abramsky, Dawar & Wang's paper, "categorical descriptions of complexity classes"