Papers for

constraint programmers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Polynomial time check for Maltsev polymorphisms in finite structures

Complexity of Deciding Existence of Maltsev Polymorphisms of Finite Relational Structures

Abstract: In this article, we show that the problem of deciding whether a finite relational structure $\mathbf{A}$ admits a Maltsev polymorphism is a computational problem, which can be solved in polynomial time. We provide a proof of this result by reducing the problem to deciding whether a binary relational structure, associated with $\mathbf{A}$ admits such a polymorphism. In our construction of such an algorithm, we make an extensive use of a property of binary relations, which is implied by the existence of a Maltsev polymorphism, the so-called rectangularity property.

Tue 10 NovComputational Complexity
The gist
This paper tackles the question of whether certain mathematical structures, called finite relational structures, have a special kind of operation known as a Maltsev polymorphism. The authors show there is an efficient algorithm that can determine this quickly, even for large structures. Their approach works by transforming the problem to a simpler one involving only pairs of elements, using a property called rectangularity. This result means checking for these polymorphisms is easier than previously thought.
Open → 2611.14379v1