A finer reduction of constraint problems to digraphs
From MaRDI portal
Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Automorphisms and endomorphisms of algebraic structures (08A35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10)
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.
Recommendations
- On the reduction of the CSP dichotomy conjecture to digraphs
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
- scientific article; zbMATH DE number 1670830
- Polymorphisms of small digraphs
- A combinatorial constraint satisfaction problem dichotomy classification conjecture
Cited in
(23)- Subset sum problems with digraph constraints
- On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
- Algebraic foundations for qualitative calculi and networks
- Galois connections for patterns: an algebra of labelled graphs
- On Maltsev digraphs
- The number of clones determined by disjunctions of unary relations
- Polymorphisms of small digraphs
- On Maltsev digraphs
- Reflexive digraphs with near unanimity polymorphisms
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- The complexity of valued CSPs
- Algebra and the complexity of digraph CSPs: a survey
- Small Promise CSPs that reduce to large CSPs
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Projection merging
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
- Binarisation for valued constraint satisfaction problems
- On the reduction of the CSP dichotomy conjecture to digraphs
- The smallest hard trees
- Generalisations of matrix partitions: complexity and obstructions
- Homogeneity and homogenizability: hard problems for the logic SNP
- Flexible constraint satisfiability and a problem in semigroup theory
- Maximal digraphs with respect to primitive positive constructability
This page was built for publication: A finer reduction of constraint problems to digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460423)
