Dualities for Constraint Satisfaction Problems

DOI10.1007/978-3-540-92800-3_5zbMath1171.68494OpenAlexW1486752157MaRDI QIDQ5504701

Andrei A. Bulatov, Andrei A. Krokhin, Benoit Larose

Publication date: 22 January 2009

Published in: Complexity of Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92800-3_5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Applications of universal algebra in computer science (08A70)

Related Items (30)

Tractability in constraint satisfaction problems: a survey ⋮ A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\) ⋮ Constraint Satisfaction Problems Solvable by Local Consistency Methods ⋮ List-homomorphism problems on graphs and arc consistency ⋮ Unnamed Item ⋮ PTAS for Sparse General-valued CSPs ⋮ NU Polymorphisms on Reflexive Digraphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Dismantlability, connectedness, and mixing in relational structures ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Boolean topological graphs of semigroups: the lack of first-order axiomatization ⋮ On Maltsev Digraphs ⋮ On the CSP Dichotomy Conjecture ⋮ Regular families of forests, antichains and duality pairs of relational structures ⋮ The complexity of the list homomorphism problem for graphs ⋮ Quasi-equational bases for graphs of semigroups, monoids and groups. ⋮ On Maltsev digraphs ⋮ There are no pure relational width 2 constraint satisfaction problems ⋮ Constraint satisfaction problems over semilattice block Mal'tsev algebras ⋮ CSP duality and trees of bounded pathwidth ⋮ Graph partitions with prescribed patterns ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ Robustly Solvable Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ On algebras with many symmetric operations ⋮ Dismantlability, Connectedness, and Mixing in Relational Structures ⋮ OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT ⋮ Recent Results on the Algebraic Approach to the CSP ⋮ Solving CSPs Using Weak Local Consistency ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the expressive power of Datalog: tools and a case study.
• There are no pure relational width 2 constraint satisfaction problems
• Bounded width problems and algebras
• Existence theorems for weakly symmetric operations
• CD(4) has bounded width
• On the complexity of H-coloring
• On classes of relations and graphs determined by subobjects and factorobjects
• Constraints, consistency and closure
• On the algebraic structure of combinatorial problems
• Characterising tractable constraints
• Homomorphisms to oriented paths
• Conjunctive-query containment and constraint satisfaction
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Datalog and constraint satisfaction with infinite templates
• On digraph coloring problems and treewidth duality
• Majority constraints have bounded pathwidth duality
• Majority functions on structures with finite duality
• Combinatorial problems raised from 2-semilattices
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability
• Parity, circuits, and the polynomial-time hierarchy
• OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A Subalgebra Intersection Property for Congruence Distributive Varieties
• Some new good characterizations for directed graphs
• The structure of finite algebras
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Posets, near unanimity functions and zigzags
• Bi‐arc graphs and the complexity of list homomorphisms
• The Existence of Homomorphisms to Oriented Cycles
• On homomorphisms to acyclic local tournaments
• Duality and Polynomial Testing of Tree Homomorphisms
• Linear Datalog and Bounded Path Duality of Relational Structures
• On tractability and congruence distributivity
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractability and Learnability Arising from Algebras with Few Subpowers
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems
• Affine Systems of Equations and Counting Infinitary Logic
• Datalog and Constraint Satisfaction with Infinite Templates
• A Characterisation of First-Order Constraint Satisfaction Problems
• Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
• Recent Results on the Algebraic Approach to the CSP
• Constraint Satisfaction Problems with Infinite Templates

This page was built for publication: Dualities for Constraint Satisfaction Problems