Authors: Jakub Bulín ; Dejan Delic ; Marcel Jackson ; Todd Niven

It is well known that the constraint satisfaction problem over a general relational structure A is polynomial time equivalent to the constraint problem over some associated digraph. We present a variant of this construction and show that the corresponding constraint satisfaction problem is logspace equivalent to that over A. Moreover, we show that almost all of the commonly encountered polymorphism properties are held equivalently on the A and the constructed digraph. As a consequence, the Algebraic CSP dichotomy conjecture as well as the conjectures characterizing CSPs solvable in logspace and in nondeterministic logspace are equivalent to their restriction to digraphs.

Comment: arXiv admin note: substantial text overlap with arXiv:1305.2039

• 05C20 - Directed graphs (digraphs), tournaments
• 05C60 - Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
• 08A35 - Automorphisms and endomorphisms of algebraic structures
• 68Q15 - Complexity classes (hierarchies, relations among complexity classes, etc.)
• 68R10 - Graph theory (including graph drawing) in computer science