7 citations · 11 across the 6 of their papers we have counts for
5 papers · 1 filter
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…
Weisfeiler-Leman Invariant Promise Valued CSPs
Libor Barto, Silvia Butti
In a recent line of work, Butti and Dalmau have shown that a fixed-template Constraint Satisfaction Problem is solvable by a certain natural linear programming relaxation (equivale…
Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the Constraint Satisfaction Problem
Silvia Butti, Victor Dalmau
Given a pair of graphs and , the problems of deciding whether there exists either a homomorphism or an isomorphism from to have r…
The Complexity of the Distributed Constraint Satisfaction Problem
Silvia Butti, Victor Dalmau
We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and…
Sparsification of Binary CSPs
Silvia Butti, Stanislav Zivny
A cut -sparsifier of a weighted graph is a re-weighted subgraph of of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of $…