Complexity of conservative constraint satisfaction problems
From MaRDI portal
Publication:2946643
DOI10.1145/1970398.1970400zbMath1351.68113OpenAlexW2032487621MaRDI QIDQ2946643
Publication date: 17 September 2015
Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1970398.1970400
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Tractability in constraint satisfaction problems: a survey ⋮ Aggregation of Votes with Multiple Positions on Each Issue ⋮ The Complexity of General-Valued CSPs ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ A Galois Connection for Valued Constraint Languages of Infinite Size ⋮ Algebraic Properties of Valued Constraint Satisfaction Problem ⋮ Unnamed Item ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ CSP for binary conservative relational structures ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ On planar valued CSPs ⋮ Minimax problems of discrete optimization invariant under majority operators ⋮ Correspondence homomorphisms to reflexive graphs ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Complexity of correspondence \(H\)-colourings ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ List homomorphisms to separable signed graphs ⋮ Conservative constraint satisfaction re-revisited ⋮ Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms ⋮ CSP beyond tractable constraint languages ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Unnamed Item ⋮ The Complexity of Valued CSPs ⋮ Bounded Tree-Width and CSP-Related Problems ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Qualitative constraint satisfaction problems: an extended framework with landmarks ⋮ On the Computational Complexity of Non-Dictatorial Aggregation ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ Minimum cost and list homomorphisms to semicomplete digraphs ⋮ Constraint satisfaction problems over semilattice block Mal'tsev algebras ⋮ Dichotomy for tree-structured trigraph list homomorphism problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Consistent query answering for primary keys in Datalog ⋮ Dichotomy for finite tournaments of mixed-type ⋮ Minimum Cost Homomorphisms with Constrained Costs ⋮ Testing the Complexity of a Valued CSP Language ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ Adjusted Interval Digraphs ⋮ Time Complexity of Constraint Satisfaction via Universal Algebra ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ A quasi-Mal'cev condition with unexpected application. ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
