Dualities for Constraint Satisfaction Problems
From MaRDI portal
Publication:5504701
DOI10.1007/978-3-540-92800-3_5zbMATH Open1171.68494OpenAlexW1486752157MaRDI QIDQ5504701FDOQ5504701
Authors: Andrei A. Bulatov, Andrei Krokhin, Benoît 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Applications of universal algebra in computer science (08A70)
Cites Work
- Title not available (Why is that?)
- Handbook of constraint programming.
- Existence theorems for weakly symmetric operations
- On the complexity of H-coloring
- Complexity classifications of Boolean constraint satisfaction problems
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Classifying the Complexity of Constraints Using Finite Algebras
- Recent Results on the Algebraic Approach to the CSP
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- Characterising tractable constraints
- Conjunctive-query containment and constraint satisfaction
- Combinatorial problems raised from 2-semilattices
- The complexity of constraint satisfaction: an algebraic approach
- The structure of finite algebras
- Title not available (Why is that?)
- Tractability and learnability arising from algebras with few subpowers
- A Characterisation of First-Order Constraint Satisfaction Problems
- Title not available (Why is that?)
- Parity, circuits, and the polynomial-time hierarchy
- On digraph coloring problems and treewidth duality
- Posets, near unanimity functions and zigzags
- Bounded width problems and algebras
- Universal Algebra and Hardness Results for Constraint Satisfaction Problems
- Bi‐arc graphs and the complexity of list homomorphisms
- On classes of relations and graphs determined by subobjects and factorobjects
- Duality theorems for finite structures (characterising gaps and good characterisations)
- Duality and Polynomial Testing of Tree Homomorphisms
- Majority constraints have bounded pathwidth duality
- From graph coloring to constraint satisfaction: there and back again
- Tame congruence theory
- A Subalgebra Intersection Property for Congruence Distributive Varieties
- Linear Datalog and Bounded Path Duality of Relational Structures
- Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability
- Title not available (Why is that?)
- Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
- Constraint Satisfaction Problems with Infinite Templates
- On tractability and congruence distributivity
- Datalog and Constraint Satisfaction with Infinite Templates
- Homomorphisms to oriented paths
- On the expressive power of Datalog: tools and a case study.
- On homomorphisms to acyclic local tournaments
- Some new good characterizations for directed graphs
- The Existence of Homomorphisms to Oriented Cycles
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- There are no pure relational width 2 constraint satisfaction problems
- Datalog and constraint satisfaction with infinite templates
- Affine Systems of Equations and Counting Infinitary Logic
- CD(4) has bounded width
- Majority functions on structures with finite duality
Cited In (41)
- List-homomorphism problems on graphs and arc consistency
- Dismantlability, Connectedness, and Mixing in Relational Structures
- Graph partitions with prescribed patterns
- Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- Dismantlability, connectedness, and mixing in relational structures
- Recent Results on the Algebraic Approach to the CSP
- Tractability in constraint satisfaction problems: a survey
- There are no pure relational width 2 constraint satisfaction problems
- Colouring, constraint satisfaction, and complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- \(n\)-permutability and linear Datalog implies symmetric Datalog
- Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
- Constraint satisfaction problems over semilattice block Mal'tsev algebras
- Title not available (Why is that?)
- Tree dualities for constraint satisfaction
- A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
- On Maltsev digraphs
- Constraint satisfaction, graph isomorphism, and the pebbling comonad
- Dualities in full homomorphisms
- PTAS for Sparse General-valued CSPs
- Solving CSPs using weak local consistency
- Near unanimity constraints have bounded pathwidth duality
- On Maltsev digraphs
- Boolean topological graphs of semigroups: the lack of first-order axiomatization
- NU polymorphisms on reflexive digraphs
- The complexity of the list homomorphism problem for graphs
- Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Quasi-equational bases for graphs of semigroups, monoids and groups.
- Algebra and the complexity of digraph CSPs: a survey
- CSP duality and trees of bounded pathwidth
- On the CSP Dichotomy Conjecture
- Robust algorithms with polynomial loss for near-unanimity CSPs
- Robustly solvable constraint satisfaction problems
- On algebras with many symmetric operations
- Regular families of forests, antichains and duality pairs of relational structures
- Finite dualities, in particular in full homomorphisms
This page was built for publication: Dualities for Constraint Satisfaction Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5504701)
