Constraint Satisfaction Problems Solvable by Local Consistency Methods
From MaRDI portal
Publication:3189638
DOI10.1145/2556646zbMath1295.68126OpenAlexW2020154454MaRDI QIDQ3189638
Publication date: 12 September 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2556646
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (57)
On a stronger reconstruction notion for monoids and clones ⋮ Tractability in constraint satisfaction problems: a survey ⋮ CLAP: A New Algorithm for Promise CSPs ⋮ The Complexity of General-Valued CSPs ⋮ A Galois Connection for Valued Constraint Languages of Infinite Size ⋮ Sherali-Adams Relaxations for Valued CSPs ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ Optimal strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties ⋮ Equivariant algorithms for constraint satisfaction problems over coset templates ⋮ Satisfiability in MultiValued Circuits ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Deciding absorption in relational structures ⋮ On Singleton Arc Consistency for CSPs Defined by Monotone Patterns ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The smallest hard trees ⋮ Constraint satisfaction problem: what makes the problem easy ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ The wonderland of reflections ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ Proof Complexity Meets Algebra ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ The Complexity of Valued CSPs ⋮ Backdoor Sets for CSP. ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems ⋮ 𝜔-categorical structures avoiding height 1 identities ⋮ DECIDING SOME MALTSEV CONDITIONS IN FINITE IDEMPOTENT ALGEBRAS ⋮ Mal'tsev conditions, lack of absorption, and solvability. ⋮ On singleton arc consistency for CSPs defined by monotone patterns ⋮ Constants and finite unary relations in qualitative constraint reasoning ⋮ A characterization of idempotent strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ Tractability of quantified temporal constraints to the max ⋮ Constraint satisfaction problems over semilattice block Mal'tsev algebras ⋮ A polynomial relational class of binary CSP ⋮ Parameterized Complexity of the Workflow Satisfiability Problem ⋮ Backdoors into heterogeneous classes of SAT and CSP ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ Dichotomy for finite tournaments of mixed-type ⋮ Robustly Solvable Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ On algebras with many symmetric operations ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ The number of clones determined by disjunctions of unary relations ⋮ Idempotent n -permutable varieties ⋮ Unnamed Item ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Solving CSPs Using Weak Local Consistency ⋮ Unnamed Item ⋮ Characterizations of several Maltsev conditions. ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
Cites Work
- Unnamed Item
- Unnamed Item
- Cyclic terms for \(\text{SD}_{\vee}\) varieties revisited
- Universal algebra and hardness results for constraint satisfaction problems
- The complexity of the conservative generalized satisfiability problem
- Combinatorial problems raised from 2-semilattices
- Closed systems of functions and predicates
- The collapse of the bounded width hierarchy
- Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Varieties with few subalgebras of powers
- Congruence Distributivity Implies Bounded Width
- The structure of finite algebras
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Constraint Satisfaction Problems of Bounded Width
- On tractability and congruence distributivity
- Classifying the Complexity of Constraints Using Finite Algebras
- Tractability and Learnability Arising from Algebras with Few Subpowers
- Robust satisfiability of constraint satisfaction problems
- A Simple Algorithm for Mal'tsev Constraints
- Recent Results on the Algebraic Approach to the CSP
- Dualities for Constraint Satisfaction Problems
This page was built for publication: Constraint Satisfaction Problems Solvable by Local Consistency Methods
