From complexity to algebra and back: digraph classes, collapsibility and the PGP

Catarina Carvalho, Florent Madelaine, Barnaby Martin

Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idempotent polymorphisms of certain digraph classes. Our fir…