A finer reduction of constraint problems to digraphs

Abstract

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.

arXiv admin note: substantial text overlap with arXiv:1305.2039

References in corpus (4)

• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• An Algebraic Theory of Complexity for Discrete Optimisation
• Maltsev digraphs have a majority polymorphism
• On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction

Cited by in corpus (8)

• Algebraic foundations for qualitative calculi and networks
• Maximal Digraphs With Respect to Primitive Positive Constructibility
• A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs
• Refuting Feder, Kinne and Rafiey
• Generalisations of Matrix Partitions : Complexity and Obstructions
• The number of clones determined by disjunctions of unary relations
• The Smallest Hard Trees
• On the complexity of $\mathbb{H}$-coloring for special oriented trees