Majority constraints have bounded pathwidth duality

DOI10.1016/j.ejc.2007.11.020zbMath1138.68052OpenAlexW1996330905MaRDI 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

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

Related Items

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

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