Charles Explorer logo
🇬🇧

Polymorphisms of small digraphs

Publication at Faculty of Mathematics and Physics |
2011

Abstract

For each digraph with at most 5 vertices, we provide a list of its polymorphisms interesting with respect to the complexity of the corresponding Constraint Satisfaction Problem. We find a digraph on six vertices such that the complexity of its retraction problem is unknown with current techniques; this is the smallest such example.