5 papers
Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
Libor Barto, Maximilian Hadek, Dmitriy Zhuk
We develop a unified framework to characterize the power of higher-level algorithms for the constraint satisfaction problem (CSP), such as -consistency, the Sherali-Adams LP hie…
Multisorted Boolean Clones Determined by Binary Relations up to Minion Homomorphisms
Libor Barto, Maryia Kapytka
We describe the ordering of a class of clones by minion homomorphisms, also known as minor preserving maps or height 1 clone homomorphisms. The class consists of all clones on fini…
The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
Kristina Asimi, Libor Barto, Victor Dalmau
We introduce the framework of the left-hand side restricted promise constraint satisfaction problem, which includes problems like approximating clique number of a graph. We study t…
The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
Libor Barto, Silvia Butti, Víctor Dalmau
In this paper we study the interactions between so-called fractional relaxations of the integer programs (IPs) which encode homomorphism and isomorphism of relational structures. W…
The Rise of Plurimorphisms: Algebraic Approach to Approximation
Libor Barto, Silvia Butti, Alexandr Kazda +2
Following the success of the so-called algebraic approach to the study of decision constraint satisfaction problems (CSPs), exact optimization of valued CSPs, and most recently pro…