Skip to main content

Research Repository

Advanced Search

All Outputs (69)

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.

The complexity of the list homomorphism problem for graphs. (2010)
Presentation / Conference Contribution
Egri, L., Krokhin, A., Larose, B., & Tesson, P. (2010, December). The complexity of the list homomorphism problem for graphs. Presented at Symposium on Theoretical Aspects of Computer Science., Nancy, France

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.

Caterpillar duality for constraint satisfaction problems (2008)
Presentation / Conference Contribution
Carvalho, C., Dalmau, V., & Krokhin, A. (2008, June). Caterpillar duality for constraint satisfaction problems. Presented at 23rd Annual IEEE Symposium on Logic in Computer Science (LICS) 2008, Pittsburgh, Pennsylvania

The study of constraint satisfaction problems definable in various fragments of Datalog has recently gained considerable importance. We consider constraint satisfaction problems that are definable in the smallest natural recursive fragment of Datalog... Read More about Caterpillar duality for constraint satisfaction problems.

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.

Dualities for constraint satisfaction problems (2008)
Book Chapter
Bulatov, A., Krokhin, A., & Larose, B. (2008). Dualities for constraint satisfaction problems. In N. Creignou, P. Kolaitis, & H. Vollmer (Eds.), Complexity of constraints : an overview of current research themes (93-124). Springer Verlag. https://doi.org/10.1007/978-3-540-92800-3_5

In a nutshell, a duality for a constraint satisfaction problem equates the existence of one homomorphism to the non-existence of other homomorphisms. In this survey paper, we give an overview of logical, combinatorial, and algebraic aspects of the fo... Read More about Dualities for constraint satisfaction problems.

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.