Polymorphisms of small digraphs (Q2853188)

Constraint satisfaction problems (CSP) form a rich class of algorithmic problems with applications in many areas of computer science. As abstract problems, CSPs are homomorphism problems for relational structures.NEWLINENEWLINE The authors provide a report on results obtained by computer testing the existence of various types of polymorphisms for small digraphs, since a digraph can be seen as a relational structure with one binary relation. The authors choose to check for polymorphisms important in CSP such as Mal'tsev polymorphism, near-unanimity polymorphisms (up to arity 5), edge polymorphisms (up to arity 5), semilattice polymorphism, and so on. The existence of these polymorphisms is checked for all non-isomorphic digraphs with up to 5 vertices, as well as for some randomly chosen digraphs on 6, 7 and 8 vertices.NEWLINENEWLINE The authors also find a digraph on six vertices such that the complexity of its retraction problem is unknown with current techniques and show that this is the smallest such example.