72 citations · 130 across the 27 of their papers we have counts for
29 papers
Parameterized Complexity Classification for Interval Constraints
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +3
Constraint satisfaction problems form a nicely behaved class of problems that lends itself to complexity classification results. From the point of view of parameterized complexity,…
Computational Short Cuts in Infinite Domain Constraint Satisfaction
Peter Jonsson, Victor Lagerkvist, Sebastian Ordyniak
A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a polynomial-time solvable class. Backdoors have found ma…
Complexity Classification Transfer for CSPs via Algebraic Products
Manuel Bodirsky, Peter Jonsson, Barnaby Martin +2
We study the complexity of infinite-domain constraint satisfaction problems: our basic setting is that a complexity classification for the CSPs of first-order expansions of a struc…
Almost Consistent Systems of Linear Equations
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an a…
Solving Infinite-Domain CSPs Using the Patchwork Property
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +1
The constraint satisfaction problem (CSP) has important applications in computer science and AI. In particular, infinite-domain CSPs have been intensively used in subareas of AI su…
Classification transfer for qualitative reasoning problems
Barnaby Martin, Peter Jonsson, Manuel Bodirsky +1
We study formalisms for temporal and spatial reasoning in the modern context of Constraint Satisfaction Problems (CSPs). We show how questions on the complexity of their subclasses…