Majority constraints have bounded pathwidth duality
From MaRDI portal
Publication:2427535
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
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