1 citations · 1 across the 4 of their papers we have counts for
4 papers
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…
Finite Algebras with Hom-Sets of Polynomial Size
Libor Barto, Antoine Mottet
We provide an internal characterization of those finite algebras (i.e., algebraic structures) such that the number of homomorphisms from any finite algebra …
Symmetries of structures that fail to interpret something finite
Libor Barto, Bertalan Bodor, Marcin Kozik +2
We investigate structural implications arising from the condition that a given directed graph does not interpret, in the sense of primitive positive interpretation with parameters…