5 citations · 6 across the 4 of their papers we have counts for
6 papers
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…
A Multivariate Complexity Analysis of Qualitative Reasoning Problems
Leif Eriksson, Victor Lagerkvist
Qualitative reasoning is an important subfield of artificial intelligence where one describes relationships with qualitative, rather than numerical, relations. Many such reasoning…
On the Strength of Uniqueness Quantification in Primitive Positive Formulas
Victor Lagerkvist, Gustav Nordh
Uniqueness quantification () is a quantifier in first-order logic where one requires that exactly one element exists satisfying a given property. In this paper we invest…
Which NP-Hard SAT and CSP Problems Admit Exponentially Improved Algorithms?
Victor Lagerkvist, Magnus Wahlström
We study the complexity of SAT() problems for potentially infinite languages closed under variable negation (sign-symmetric languages). Via an algebraic connection, this red…
Kernelization of Constraint Satisfaction Problems: A Study through Universal Algebra
Victor Lagerkvist, Magnus Wahlström
A kernelization algorithm for a computational problem is a procedure which compresses an instance into an equivalent instance whose size is bounded with respect to a complexity par…
Time Complexity of Constraint Satisfaction via Universal Algebra
Peter Jonsson, Victor Lagerkvist, Biman Roy
The exponential-time hypothesis (ETH) states that 3-SAT is not solvable in subexponential time, i.e. not solvable in O(c^n) time for arbitrary c > 1, where n denotes the number of…