Majority constraints have bounded pathwidth duality

DOI10.1016/j.ejc.2007.11.020zbMath1138.68052MaRDI QIDQ2427535

Andrei A. Krokhin, Victor Dalmau

Publication date: 13 May 2008

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10230/36342

zbMATH Keywords

constraint satisfaction problems

Mathematics Subject Classification ID

68T27: Logic in artificial intelligence

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

Unnamed Item, Solving CSPs Using Weak Local Consistency, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Dualities for Constraint Satisfaction Problems, List-homomorphism problems on graphs and arc consistency, Maltsev digraphs have a majority polymorphism, The complexity of the list homomorphism problem for graphs, CSP duality and trees of bounded pathwidth, A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\), On Maltsev digraphs, Majority functions on structures with finite duality, On Maltsev Digraphs, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounded width problems and algebras
• Constraints, consistency and closure
• On the algebraic structure of combinatorial problems
• Conjunctive-query containment and constraint satisfaction
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• First-order Definable Retraction Problems for Posets and Reflexive Graphs
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Bi‐arc graphs and the complexity of list homomorphisms
• Linear Datalog and Bounded Path Duality of Relational Structures
• On tractability and congruence distributivity
• Classifying the Complexity of Constraints Using Finite Algebras
• A Characterisation of First-Order Constraint Satisfaction Problems