Constraint Satisfaction, Graph Isomorphism, and the Pebbling Comonad
Abstract
Description
The pebbling comonad introduced in (Abramsky, Dawar, Wang 2017) gives a categorical account relating natural approximations of homomorphism and isomorphism. On the one hand we have the local consistency algorithms that approximate homomorphism and on the other the Weisfeiler–Leman algorithms that approximate isomorphism. Both of these have elegant characterizations as pebble games. In this paper we give a brief tour through the background that led to the definition of the pebbling comonad and look at some prospects it offers.