From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP
From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP
Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idem potent polymorphisms of certain digraph classes. Our first results are two algebraic dichotomy, even "gap", theorems. Building on and extending [Martin CP'11], we prove that partially reflexive paths bequeath a set of idem …