A finer reduction of constraint problems to digraphs

DOI10.2168/LMCS-11(4:18)2015zbMath1409.05094arXiv1406.6413OpenAlexW1791050365MaRDI QIDQ3460423

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

Publication date: 7 January 2016

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

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

zbMATH Keywords

polymorphismdirected graphconstraint satisfaction problemdichotomy conjecture

Mathematics Subject Classification ID

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

Related Items

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, On the complexity of \(\mathbb{H}\)-coloring for special oriented trees, Unnamed Item, The smallest hard trees, Binarisation for Valued Constraint Satisfaction Problems, Reflexive digraphs with near unanimity polymorphisms, The Complexity of Valued CSPs, Algebra and the Complexity of Digraph CSPs: a Survey, Algebraic foundations for qualitative calculi and networks, Galois connections for patterns: an algebra of labelled graphs, The number of clones determined by disjunctions of unary relations