Constraint satisfaction problems over semilattice block Mal'tsev algebras

DOI10.1016/J.IC.2019.104437zbMATH Open1434.68191arXiv1701.02623OpenAlexW2967773100WikidataQ127368966 ScholiaQ127368966MaRDI QIDQ2272992FDOQ2272992

Authors: Andrei A. Bulatov 

Publication date: 17 September 2019

Published in: Information and Computation (Search for Journal in Brave)

Abstract: There are two well known types of algorithms for solving CSPs: local propagation and generating a basis of the solution space. For several years the focus of the CSP research has been on `hybrid' algorithms that somehow combine the two approaches. In this paper we present a new method of such hybridization that allows us to solve certain CSPs that has been out of reach for a quite a while. We consider these method on a fairly restricted class of CSPs given by algebras we will call semilattice block Mal'tsev. An algebra A is called semilattice block Mal'tsev if it has a binary operation f, a ternary operation m, and a congruence s such that the quotient A/s with operation $f$ is a semilattice, $f$ is a projection on every block of s, and every block of s is a Mal'tsev algebra with Mal'tsev operation m. We show that the constraint satisfaction problem over a semilattice block Mal'tsev algebra is solvable in polynomial time.

Full work available at URL: https://arxiv.org/abs/1701.02623

Recommendations

• Constraint satisfaction problems over semilattice block Mal'tsev algebras
• scientific article; zbMATH DE number 1670830
• A proof of the CSP dichotomy conjecture
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Constraint satisfaction problems: complexity and algorithms

zbMATH Keywords

constraint satisfaction problemdichotomy conjectureblock-minimalitysemilattice block Mal'tsev algebras

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Equational logic, Mal'tsev conditions (08B05) Computational aspects of satisfiability (68R07)

Cites Work

• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Title not available (Why is that?)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• Recent Results on the Algebraic Approach to the CSP
• Complexity of conservative constraint satisfaction problems
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The structure of finite algebras
• Monotone monadic SNP and constraint satisfaction
• Tractability and learnability arising from algebras with few subpowers
• A Simple Algorithm for Mal'tsev Constraints
• Dualities for Constraint Satisfaction Problems
• Conservative constraint satisfaction re-revisited
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Three-element Mal'tsev algebras
• A combinatorial constraint satisfaction problem dichotomy classification conjecture
• An algebraic approach to multi-sorted constraints
• Title not available (Why is that?)
• A proof of the CSP dichotomy conjecture

Cited In (5)

• Non-local configuration of component interfaces by constraint satisfaction
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• A Simple Algorithm for Mal'tsev Constraints
• Combinatorial problems raised from 2-semilattices
• Constraint satisfaction problems over semilattice block Mal'tsev algebras

This page was built for publication: Constraint satisfaction problems over semilattice block Mal'tsev algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272992)