Skip to main content

Research Repository

Advanced Search

Professor Andrei Krokhin's Outputs (42)

Topology and adjunction in promise constraint satisfaction (2023)
Journal Article
Krokhin, A., Opršal, J., Wrochna, M., & Živný, S. (2023). Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing, 52(1), 38-79. https://doi.org/10.1137/20m1378223

The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a c-colouring of a graph that is promised to be k-colourable, where c≥k. This problem naturally generalises to promise graph homomorphism problems... Read More about Topology and adjunction in promise constraint satisfaction.

Algebraic Approach to Promise Constraint Satisfaction (2021)
Journal Article
Barto, L., Bulín, J., Krokhin, A., & Opršal, J. (2021). Algebraic Approach to Promise Constraint Satisfaction. Journal of the ACM, 68(4), 1-66. https://doi.org/10.1145/3457606

The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the past 20 years. A new version of the CSP, the promise CSP (PCSP), has recently been proposed, motivated by open questions about the appr... Read More about Algebraic Approach to Promise Constraint Satisfaction.

Robust algorithms with polynomial loss for near-unanimity CSPs (2019)
Journal Article
Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y., & Oprsal, J. (2019). Robust algorithms with polynomial loss for near-unanimity CSPs. SIAM Journal on Computing, 48(6), 1763-1795. https://doi.org/10.1137/18m1163932

An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a xed domain to the variables so that all constraints are satised. In the optimizatio... Read More about Robust algorithms with polynomial loss for near-unanimity CSPs.

Towards a characterization of constant-factor approximable Finite-Valued CSPs (2018)
Journal Article
Dalmau, V., Krokhin, A., & Manokaran, R. (2018). Towards a characterization of constant-factor approximable Finite-Valued CSPs. Journal of Computer and System Sciences, 97, 14-27. https://doi.org/10.1016/j.jcss.2018.03.003

We study the approximability of (Finite-)Valued Constraint Satisfaction Problems (VCSPs) with a fixed finite constraint language Γ consisting of finitary functions on a fixed finite domain. Ene et al. have shown that, under a mild technical condition... Read More about Towards a characterization of constant-factor approximable Finite-Valued CSPs.

Binarisation for Valued Constraint Satisfaction Problems (2017)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., Krokhin, A., Powell, R., & Zivny, S. (2017). Binarisation for Valued Constraint Satisfaction Problems. SIAM Journal on Discrete Mathematics, 31(4), 2279-2300. https://doi.org/10.1137/16m1088107

We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the algebraic properties that capture the computational complexity of VCSPs. S... Read More about Binarisation for Valued Constraint Satisfaction Problems.

The complexity of general-valued CSPs (2017)
Journal Article
Kolmogorov, V., Krokhin, A., & Rolínek, M. (2017). The complexity of general-valued CSPs. SIAM Journal on Computing, 46(3), 1087-1110. https://doi.org/10.1137/16m1091836

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 on a subset of the variables. Each function can take finite values spec... Read More about The complexity of general-valued CSPs.

On algebras with many symmetric operations (2016)
Journal Article
Carvalho, C., & Krokhin, A. (2016). On algebras with many symmetric operations. International Journal of Algebra and Computation, 26(05), 1019-1032. https://doi.org/10.1142/s0218196716500429

An n-ary operation f is called symmetric if, for all permutations π of {1, . . . , n}, it satisfies the identity f(x1, x2, . . . , xn) = f(xπ(1), xπ(2), . . . , xπ(n) ). We show that, for each finite algebra A, either it has symmetric term operations... Read More about On algebras with many symmetric operations.

Characterizations of several Maltsev conditions (2015)
Journal Article
Kozik, M., Krokhin, A., Valeriote, M., & Willard, R. (2015). Characterizations of several Maltsev conditions. Algebra Universalis, 73(3), 205-224. https://doi.org/10.1007/s00012-015-0327-2

ame congruence theory identifies six Maltsev conditions associated with locally finite varieties omitting certain types of local behaviour. Extending a result of Siggers, we show that of these six Maltsev conditions only two of them are equivalent to... Read More about Characterizations of several Maltsev conditions.

Oracle Tractability of Skew Bisubmodular Functions (2014)
Journal Article
Huber, A., & Krokhin, A. (2014). Oracle Tractability of Skew Bisubmodular Functions. SIAM Journal on Discrete Mathematics, 28(4), 1828-1837. https://doi.org/10.1137/130936038

In this paper we consider skew bisubmodular functions as recently introduced by the authors and Powell. We construct a convex extension of a skew bisubmodular function which we call Lovász extension in correspondence to the submodular case. We use th... Read More about Oracle Tractability of Skew Bisubmodular Functions.

The Complexity of Valued Constraint Satisfaction (2014)
Journal Article
Jeavons, P., Krokhin, A., & Živný, S. (2014). The Complexity of Valued Constraint Satisfaction. Bulletin of the European Association for Theoretical Computer Science, 113, 21-55

We survey recent results on the broad family of problems that can be cast as valued constraint satisfaction problems. We discuss general methods for analysing the complexity of such problems, give examples of tractable cases, and identify general fea... Read More about The Complexity of Valued Constraint Satisfaction.

Skew Bisubmodularity and Valued CSPs (2014)
Journal Article
Huber, A., Krokhin, A., & Powell, R. (2014). Skew Bisubmodularity and Valued CSPs. SIAM Journal on Computing, 43(3), 1064-1084. https://doi.org/10.1137/120893549

An instance of the (finite-)valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of values, and a sum of (rational-valued) functions, with each function depending on a subset of the variables. The goal... Read More about Skew Bisubmodularity and Valued CSPs.

Robust Satisfiability for CSPs: Hardness and Algorithmic Results (2013)
Journal Article
Dalmau, V., & Krokhin, A. (2013). Robust Satisfiability for CSPs: Hardness and Algorithmic Results. ACM Transactions on Computation Theory, 5(4), Article 15. https://doi.org/10.1145/2540090

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least a (1 − f(ε))-fraction of constraints for each (1 − ε)-satisfiable instance (i.e., such that at most a ε-fraction of constraints needs... Read More about Robust Satisfiability for CSPs: Hardness and Algorithmic Results.

CSP duality and trees of bounded pathwidth. (2010)
Journal Article
Carvalho, C., Dalmau, V., & Krokhin, A. (2010). CSP duality and trees of bounded pathwidth. Theoretical Computer Science, 411(34-36), 3188-3208. https://doi.org/10.1016/j.tcs.2010.05.016

We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of bounded pathwidth and in algeb... Read More about CSP duality and trees of bounded pathwidth..

Hard constraint satisfaction problems have hard gaps at location 1 (2009)
Journal Article
Jonsson, P., Krokhin, A., & Kuivinen, F. (2009). Hard constraint satisfaction problems have hard gaps at location 1. Theoretical Computer Science, 410(38-40), 3856-3874. https://doi.org/10.1016/j.tcs.2009.05.022

An instance of the maximum constraint satisfaction problem (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 constraints. Max CSP captures m... Read More about Hard constraint satisfaction problems have hard gaps at location 1.

The complexity of constraint satisfaction games and QCSP (2009)
Journal Article
Boerner, F., Bulatov, A., Chen, H., Jeavons, P., & Krokhin, A. (2009). The complexity of constraint satisfaction games and QCSP. Information and Computation, 207(9), 923-944. https://doi.org/10.1016/j.ic.2009.05.003

We study the complexity of two-person constraint satisfaction games. An instance of such a game is given by a collection of constraints on overlapping sets of variables, and the two players alternately make moves assigning values from a finite domain... Read More about The complexity of constraint satisfaction games and QCSP.

The approximability of MAX CSP with fixed-value constraints (2008)
Journal Article
Deineko, V., Jonsson, P., Klasson, M., & Krokhin, A. (2008). The approximability of MAX CSP with fixed-value constraints. Journal of the ACM, 55(4), Article 16. https://doi.org/10.1145/1391289.1391290

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 assign values from a given finite domain to the variables so as to maxi... Read More about The approximability of MAX CSP with fixed-value constraints.

Computational complexity of auditing finite attributes in statistical databases (2008)
Journal Article
Jonsson, P., & Krokhin, A. (2008). Computational complexity of auditing finite attributes in statistical databases. Journal of Computer and System Sciences, 74(5), 898-909. https://doi.org/10.1016/j.jcss.2008.02.002

We study the computational complexity of auditing finite attributes in databases allowing statistical queries. Given a database that supports statistical queries, the auditing problem is to check whether an attribute can be completely determined or n... Read More about Computational complexity of auditing finite attributes in statistical databases.

Retractions onto series-parallel posets (2008)
Journal Article
Dalmau, V., Krokhin, A., & Larose, B. (2008). Retractions onto series-parallel posets. Discrete Mathematics, 308(11), 2104-2114. https://doi.org/10.1016/j.disc.2006.08.010

The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite serie... Read More about Retractions onto series-parallel posets.

Majority constraints have bounded pathwidth duality (2008)
Journal Article
Dalmau, V., & Krokhin, A. (2008). Majority constraints have bounded pathwidth duality. European Journal of Combinatorics, 29(4), 821-837. https://doi.org/10.1016/j.ejc.2007.11.020

We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that such a problem is equivalent to... Read More about Majority constraints have bounded pathwidth duality.

Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction (2008)
Journal Article
Krokhin, A., & Larose, B. (2008). Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction. SIAM Journal on Discrete Mathematics, 22(1), 312-328. https://doi.org/10.1137/060669565

Recently, a strong link has been discovered between supermodularity on lattices and tractability of optimization problems known as maximum constraint satisfaction problems. This paper strengthens this link. We study the problem of maximizing a superm... Read More about Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction.

Complexity of clausal constraints over chains (2008)
Journal Article
Creignou, N., Hermann, M., Krokhin, A., & Salzer, G. (2008). Complexity of clausal constraints over chains. Theory of Computing Systems, 42(2), 239-255. https://doi.org/10.1007/s00224-007-9003-z

We investigate the complexity of the satisfiability problem of constraints over finite totally ordered domains. In our context, a clausal constraint is a disjunction of inequalities of the form x≥d and x≤d. We classify the complexity of constraints b... Read More about Complexity of clausal constraints over chains.

Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights (2007)
Journal Article
Jonsson, P., & Krokhin, A. (2007). Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. Journal of Computer and System Sciences, 73(5), 691-702. https://doi.org/10.1016/j.jcss.2007.02.001

In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of positive-weight constraints on overlapping sets of variables, and the goal is to assign values from a given domain to the variables so that the total weight... Read More about Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights.

First-order definable retraction problems for posets and reflexive graphs (2007)
Journal Article
Dalmau, V., Krokhin, A., & Larose, B. (2007). First-order definable retraction problems for posets and reflexive graphs. Journal of Logic and Computation, 17(1), 31-51. https://doi.org/10.1093/logcom/exl014

A retraction from a structure P to its substructure Q is a homomorphism from P onto Q that is the identity on Q. We present an algebraic condition which completely characterzies all posets and all reflexive graphs Q such that the class of all posets... Read More about First-order definable retraction problems for posets and reflexive graphs.

The complexity of soft constraint satisfaction (2006)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2006). The complexity of soft constraint satisfaction. Artificial Intelligence, 170(11), 983-1016. https://doi.org/10.1016/j.artint.2006.04.002

Over the past few years there has been considerable progress in methods to systematically analyse the complexity of constraint satisfaction problems with specified constraint types. One very powerful theoretical development in this area links the com... Read More about The complexity of soft constraint satisfaction.

Supermodular functions and the complexity of MAX CSP (2005)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2005). Supermodular functions and the complexity of MAX CSP. Discrete Applied Mathematics, 149(1-3), 53-72. https://doi.org/10.1016/j.dam.2005.03.003

In this paper we study the complexity of the maximum constraint satisfaction problem (MAX CSP) over an arbitrary finite domain. An instance of MAX CSP consists of a set of variables and a collection of constraints which are applied to certain specifi... Read More about Supermodular functions and the complexity of MAX CSP.

Classifying the complexity of constraints using finite algebras (2005)
Journal Article
Bulatov, A., Jeavons, P., & Krokhin, A. (2005). Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34(3), 720-742. https://doi.org/10.1137/s0097539700376676

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. Here we show that... Read More about Classifying the complexity of constraints using finite algebras.

Complexity classification in qualitative temporal constraint reasoning (2004)
Journal Article
Jonsson, P., & Krokhin, A. (2004). Complexity classification in qualitative temporal constraint reasoning. Artificial Intelligence, 160(1-2), 35-51. https://doi.org/10.1016/j.artint.2004.05.010

We study the computational complexity of the qualitative algebra which is a temporal constraint formalism that combines the point algebra, the point-interval algebra and Allen's interval algebra. We identify all tractable fragments and show that ever... Read More about Complexity classification in qualitative temporal constraint reasoning.

Recognizing frozen variables in constraint satisfaction problems (2004)
Journal Article
Jonsson, P., & Krokhin, A. (2004). Recognizing frozen variables in constraint satisfaction problems. Theoretical Computer Science, 329(1-3), 93-113. https://doi.org/10.1016/j.tcs.2004.08.006

In constraint satisfaction problems over finite domains, some variables can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constra... Read More about Recognizing frozen variables in constraint satisfaction problems.

A maximal tractable class of soft constraints (2004)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2004). A maximal tractable class of soft constraints. Journal of Artificial Intelligence Research, 22, 1-22. https://doi.org/10.1613/jair.1400

Many researchers in artificial intelligence are beginning to explore the use of soft constraints to express a set of (possibly conflicting) problem requirements. A soft constraint is a function defined on a collection of variables which associates so... Read More about A maximal tractable class of soft constraints.

Constraint satisfaction problems on intervals and lengths (2004)
Journal Article
Krokhin, A., Jeavons, P., & Jonsson, P. (2004). Constraint satisfaction problems on intervals and lengths. SIAM Journal on Discrete Mathematics, 17(3), 453-477. https://doi.org/10.1137/s0895480102410201

We study interval-valued constraint satisfaction problems (CSPs), in which the aim is to find an assignment of intervals to a given set of variables subject to constraints on the relative positions of intervals. Many well-known problems such as INTER... Read More about Constraint satisfaction problems on intervals and lengths.

Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra (2003)
Journal Article
Krokhin, A., Jeavons, P., & Jonsson, P. (2003). Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra. Journal of the ACM, 50(5), 591-640. https://doi.org/10.1145/876638.876639

Allen's interval algebra is one of the best established formalisms for temporal reasoning. This article provides the final step in the classification of complexity for satisfiability problems over constraints expressed in this algebra. When the const... Read More about Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra.

A monoidal interval of isotone clones on a finite chain (2002)
Journal Article
Krokhin, A., & Larose, B. (2002). A monoidal interval of isotone clones on a finite chain. Acta scientiarum mathematicarum, 68(1-2), 37-62

Let k denote a k-element chain, k3. Let M denote the clone generated by all unary isotone operations on k and let Pol denote the clone of all isotone operations on k. We investigate the interval of clones [MPol]. Among other results, we describe comp... Read More about A monoidal interval of isotone clones on a finite chain.