A finer reduction of constraint problems to digraphs

DOI10.2168/LMCS-11(4:18)2015zbMATH Open1409.05094arXiv1406.6413OpenAlexW1791050365MaRDI QIDQ3460423FDOQ3460423

Authors: Jakub Bulín, Dejan Delić, Marcel Jackson, Todd Niven 

Publication date: 7 January 2016

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1406.6413

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

zbMATH Keywords

directed graphpolymorphismconstraint satisfaction problemdichotomy conjecture

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) 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)

Cited In (19)

• The number of clones determined by disjunctions of unary relations
• Generalisations of matrix partitions: complexity and obstructions
• Algebraic foundations for qualitative calculi and networks
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Title not available (Why is that?)
• Subset sum problems with digraph constraints
• On Maltsev digraphs
• Binarisation for valued constraint satisfaction problems
• The smallest hard trees
• Polymorphisms of small digraphs
• Galois connections for patterns: an algebra of labelled graphs
• On Maltsev digraphs
• Reflexive digraphs with near unanimity polymorphisms
• Projection merging
• The complexity of valued CSPs
• On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
• On the reduction of the CSP dichotomy conjecture to digraphs
• Algebra and the complexity of digraph CSPs: a survey
• Complexity and polymorphisms for digraph constraint problems under some basic constructions

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)