2013/05/09 by Jakub Bulin, Jakub Bulín, Dejan Delic +7
Computer Science · Mathematics · #05C20 #05C60 #08A35 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #F.1.3 #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Logic, programming, and type systems #acm:05C20 #acm:05C60 #acm:08A35 #cs.CC #math.CO #msc:05C20 #msc:05C60 #msc:08A35
paper · pdf · doi:10.48550/arxiv.1305.2039
34 pages. Article is to appear in CP2013. This version includes two appendices with proofs of claims omitted from the main article
openalex publication_date 2013/05/09 · arxiv created 2013/08/02 · arxiv updated 2013/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is well known that the constraint satisfaction problem over general relational structures can be reduced in polynomial time to digraphs. We present a simple variant of such a reduction and use it to show that the algebraic dichotomy conjecture is equivalent to its restriction to digraphs and that the polynomial reduction can be made in logspace. We also show that our reduction preserves the bounded width property, i.e., solvability by local consistency methods. We discuss further algorithmic properties that are preserved and related open problems.