75 citations · 210 across the 10 of their papers we have counts for
3 papers · 1 filter
Even Delta-Matroids and the Complexity of Planar Boolean CSPs
Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek
The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each vari…
Effectiveness of Structural Restrictions for Hybrid CSPs
Vladimir Kolmogorov, Michal Rolinek, Rustem Takhanov
Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism…
The Complexity of General-Valued CSPs
Vladimir Kolmogorov, Andrei Krokhin, Michal Rolinek
An instance of the Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending o…