20 citations · 43 across the 29 of their papers we have counts for
5 papers · 1 filter
The algebraic structure of the densification and the sparsification tasks for CSPs
Rustem Takhanov
The tractability of certain CSPs for dense or sparse instances is known from the 90s. Recently, the densification and the sparsification of CSPs were formulated as computational ta…
On the induced problem for fixed-template CSPs
Rustem Takhanov
The Constraint Satisfaction Problem (CSP) is a problem of computing a homomorphism between two relational structures, where is defined over a…
Hybrid VCSPs with crisp and conservative valued templates
Rustem Takhanov
A constraint satisfaction problem (CSP) is a problem of computing a homomorphism between two relational structures. Analyzing its complexity has been…
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…
Extensions of the Minimum Cost Homomorphism Problem
Rustem Takhanov
Assume is a finite set and is a finite set of functions from to the natural numbers. An instance of the minimum -cost homomorphism problem () is a set of v…