A new algorithm for constraint satisfaction problems with Maltsev templates

In this article, we provide a new algorithm for solving constraint satisfaction problems with Maltsev constraints, based on the new notion of Maltsev consistency.

Computer Science Mathematics

View graph Source

Paper

References (18)

01Idempotent Simple AlgebrasK. Kearnes2017 · 14 citations

02Limitations of Algebraic Approaches to Graph Isomorphism TestingChristoph Berkholz, Martin Grohe2015 · International Colloquium on Automata, Languages and Programming · 46 citations

03Constraint Satisfaction Problems Solvable by Local Consistency MethodsL. Barto, M. Kozik2014 · Journal of the ACM · 198 citations

04Universal Algebra: Fundamentals and Selected TopicsC. Bergman2011 · 206 citations

05Constraint Satisfaction Problems of Bounded WidthL. Barto, M. Kozik2009 · 2009 50th Annual IEEE Symposium on Foundations of Computer Science · 157 citations

06Varieties with few subalgebras of powersJ. Berman, P. Idziak, P. Marković et al.2009 · 149 citations

07A Simple Algorithm for Mal'tsev ConstraintsA. Bulatov, V. Dalmau2006 · SIAM journal on computing (Print) · 163 citations

08Undirected ST-connectivity in log-spaceOmer Reingold2005 · Symposium on the Theory of Computing · 307 citations

09Classifying the Complexity of Constraints Using Finite AlgebrasA. Bulatov, P. Jeavons, A. Krokhin2005 · SIAM journal on computing (Print) · 605 citations

10A course in universal algebraS. Burris, H. P. Sankappanavar1981 · Graduate texts in mathematics · 3.3k citations

11The complexity of satisfiability problemsT. Schaefer1978 · Symposium on the Theory of Computing · 2.1k citations

12Is Polynomial Time Choiceless?E. Grädel, Martin Grohe2015 · Fields of Logic and Computation II · 21 citations

Scroll for more · 6 remaining

Similar papers

A new algorithm for constraint satisfaction problems with few subpowers templatesD. Delic, Amir El-Aooiti2017 · arXiv: Logic · 0 citations In Library

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev BlocksPetar Markovi'c, Mikl'os Mar'oti, Ralph McKenzie et al.2026 · arXiv.org · 1 citation In Library

Conservative Maltsev Constraint Satisfaction ProblemsM. Bodirsky, Andrew Moorhead2025 · arXiv.org · 1 citation In Library

Constraint satisfaction problems over semilattice block Mal'tsev algebrasA. Bulatov2017 · Logic in Computer Science · 12 citations In Library

The Meta-Problem for Conservative Mal'tsev ConstraintsClément Carbonnel2016 · AAAI Conference on Artificial Intelligence · 6 citations In Library

Distance constraint satisfaction problemsM. Bodirsky, V. Dalmau, Barnaby Martin et al.2010 · Information and Computation · 10 citations In Library

Singleton algorithms for the Constraint Satisfaction ProblemDmitriy Zhuk2025 · arXiv.org · 4 citations In Library

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction ProblemsMoritz Lichter, Benedikt Pago2024 · International Colloquium on Automata, Languages and Programming · 5 citations In Library

Constraint Satisfaction Problems Solvable by Local Consistency MethodsL. Barto, M. Kozik2014 · Journal of the ACM · 198 citations In Library

Equivariant algorithms for constraint satisfaction problems over coset templatesS. Lasota2014 · Information Processing Letters · 1 citation In Library

Patents near this paper

REFORMULATION OF CONSTRAINT SATISFACTION PROBLEMS FOR STOCHASTIC SEARCHUS 7,587,376 · INTERNATIONAL BUSINESS MACHINES CORPORATION · 2009 CONSTRAINT SATISFACTION PROBLEM SOLVING USING CONSTRAINT SEMANTICSUS 8,781,986 · INTERNATIONAL BUSINESS MACHINES CORPORATION · 2014 METHOD AND APPARATUS FOR SOLVING CONSTRAINTSUS 7,107,553 · SYNOPSYS, INC. · 2006 METHOD, APPARATUS AND PRODUCT FOR SAT SOLVING USING TEMPLATES CLAUSESUS 8,407,175 · INTERNATIONAL BUSINESS MACHINES CORPORATION · 2013 METHOD AND APPARATUS FOR SOLVING CONSTRAINTSUS 7,257,786 · SYNOPSYS, INC. · 2007

Source of record

arXiv