13 papers
Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak +3
Determining the validity of a quantified Boolean formula (QBF) is a PSPACE-complete problem with rich expressive power. Despite interest in efficient solvers, there is, compared to…
Backdoors for Quantified Boolean Formulas
Leif Eriksson, Victor Lagerkvist, Sebastian Ordyniak +3
The quantified Boolean formula problem (QBF) is a well-known PSpace-complete problem with rich expressive power, and is generally viewed as the SAT analogue for PSpace. Given that…
Optimal FPT-Approximability for Modular Linear Equations
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
We show optimal FPT-approximability results for solving almost satisfiable systems of modular linear equations, completing the picture of the parameterized complexity and FPT-appro…
Parameterized Approximability for Modular Linear Equations
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
We consider the Min--Lin problem: given a system of length- linear equations modulo , find of minimum cardinality such that is satisfiable…
Towards a Parameterized Approximation Dichotomy of MinCSP for Linear Equations over Finite Commutative Rings
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +2
We consider the MIN-r-LIN(R) problem: given a system S of length-r linear equations over a ring R, find a subset of equations Z of minimum cardinality such that S-Z is satisfiable.…
CSPs with Few Alien Constraints
Peter Jonsson, Victor Lagerkvist, George Osipov
The constraint satisfaction problem asks to decide if a set of constraints over a relational structure is satisfiable (CSP). We consider CSP$(\mathcal{…
Solving Quantified Boolean Formulas with Few Existential Variables
Leif Eriksson, Victor Lagerkvist, George Osipov +3
The quantified Boolean formula (QBF) problem is an important decision problem generally viewed as the archetype for PSPACE-completeness. Many problems of central interest in AI are…
Algorithms and Complexity of Difference Logic
Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak +1
Difference Logic (DL) is a fragment of linear arithmetics where atoms are constraints x+k <= y for variables x,y (ranging over Q or Z) and integer k. We study the complexity of dec…
Parameterized Complexity of MinCSP over the Point Algebra
George Osipov, Marcin Pilipczuk, Magnus Wahlström
The input in the Minimum-Cost Constraint Satisfaction Problem (MinCSP) over the Point Algebra contains a set of variables, a collection of constraints of the form , ,…
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,…
Parameterized Complexity of Equality MinCSP
George Osipov, Magnus Wahlström
We study the parameterized complexity of MinCSP for so-called equality languages, i.e., for finite languages over an infinite domain such as , where the relations are d…
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…