78 citations · 116 across the 14 of their papers we have counts for
12 papers · 1 filter
An invitation to the promise constraint satisfaction problem
Andrei Krokhin, Jakub Opršal
The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. Afte…
Topology and adjunction in promise constraint satisfaction
Andrei Krokhin, Jakub Opršal, Marcin Wrochna +1
The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a -colouring of a graph that is promised to be -colourable, where $c\g…
The complexity of 3-colouring -colourable graphs
Andrei Krokhin, Jakub Opršal
We study the complexity of approximation on satisfiable instances for graph homomorphism problems. For a fixed graph , the -colouring problem is to decide whether a given gra…
Algebraic approach to promise constraint satisfaction
Libor Barto, Jakub Bulín, Andrei Krokhin +1
The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the last 20 years. A new version of the CSP, the promise CSP (PCSP) h…
Towards a Characterization of Constant-Factor Approximable Finite-Valued CSPs
Victor Dalmau, Andrei Krokhin, Rajsekar Manokaran
In this paper we study the approximability of (Finite-)Valued Constraint Satisfaction Problems (VCSPs) with a fixed finite constraint language Γ consisting of finitary functions on…
A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs
Robert Powell, Andrei Krokhin
In a valued constraint satisfaction problem (VCSP), the goal is to find an assignment of labels to variables that minimizes a given sum of functions. Each function in the sum depen…
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…
Oracle Tractability of Skew Bisubmodular Functions
Anna Huber, Andrei Krokhin
In this paper we consider skew bisubmodular functions as introduced in [9]. We construct a convex extension of a skew bisubmodular function which we call Lovász extension in corres…
The complexity of the list homomorphism problem for graphs
Laszlo Egri, Andrei Krokhin, Benoit Larose +1
We completely classify the computational complexity of the list H-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph H the pro…
Hard constraint satisfaction problems have hard gaps at location 1
Peter Jonsson, Andrei Krokhin, Fredrik Kuivinen
An instance of Max CSP is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constra…
The approximability of MAX CSP with fixed-value constraints
Vladimir Deineko, Peter Jonsson, Mikael Klasson +1
In the maximum constraint satisfaction problem (MAX CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to a…
The approximability of three-valued MAX CSP
Peter Jonsson, Mikael Klasson, Andrei Krokhin
In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to a…