5 citations · 7 across the 24 of their papers we have counts for
28 papers
A Fast Algorithm for Maltsev Constraints
Victor Lagerkvist
The constraint satisfaction problem over a set of relations (CSP()) is the computational problem of deciding if a set of constraints admits at least one solution. The classi…
Maximum Satisfiability of Simple Temporal Problems
Johannes K. Fichte, Johanna Groven, Peter Jonsson +2
The Simple Temporal Problem (STP) is a core framework for quantitative temporal constraints. As STP data can be inconsistent, we study MAXSTP: compute a maximum-cardinality consist…
Representative Sets in Propositional Abduction
Johannes Schmidt, Mohamed Maizia, Victor Lagerkvist +1
The propositional abduction problem is a well-known form of non-monotonic reasoning where we are asked to find an explanation of a given manifestation. Recently, there has been an…
Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
Victor Lagerkvist, Johanna Groven, Leif Eriksson
The region connection calculus () and Allen's interval algebra () are two well-known NP-hard spatial-temporal qualitative reasoning problems. They are solvable in $2^{O(n…
Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen +2
We say that an instance of a constraint satisfaction problem (CSP) is non-redundant if the satisfaction of each clause cannot be implied by the satisfaction of the other clauses in…
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…
New Perspectives on Semiring Applications to Dynamic Programming
Ambroise Baril, Miguel Couceiro, Victor Lagerkvist
Semiring algebras have been shown to provide a suitable language to formalize many noteworthy combinatorial problems. For instance, the Shortest-Path problem can be seen as a speci…
Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
Ambroise Baril, Miguel Couceiro, Victor Lagerkvist
The -Coloring problem is a well-known generalization of the classical NP-complete problem -Coloring where the task is to determine whether an input graph admits a homomorphis…
Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
Peter Jonsson, Victor Lagerkvist, Jorke M. de Vlas +1
We study a model of constraint satisfaction problems geared towards instances with few variables but with domain of unbounded size (udCSP). Our model is inspired by recent work on…
Complexity of Faceted Explanations in Propositional Abduction
Johannes Schmidt, Mohamed Maizia, Victor Lagerkvist +1
Abductive reasoning is a popular non-monotonic paradigm that aims to explain observed symptoms and manifestations. It has many applications, such as diagnosis and planning in artif…
The Richness of CSP Non-redundancy
Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen +2
In the field of constraint satisfaction problems (CSP), a clause is called redundant if its satisfaction is implied by satisfying all other clauses. An instance of CSP is call…
Facets in Argumentation: A Formal Approach to Argument Significance
Johannes Fichte, Nicolas Fröhlich, Markus Hecher +4
Argumentation is a central subarea of Artificial Intelligence (AI) for modeling and reasoning about arguments. The semantics of abstract argumentation frameworks (AFs) is given by…
A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
Victor Lagerkvist, Mohamed Maizia, Johannes Schmidt
The Boolean satisfiability problem (SAT) is a well-known example of monotonic reasoning, of intense practical interest due to fast solvers, complemented by rigorous fine-grained co…
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…
The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
Ambroise Baril, Miguel Couceiro, Victor Lagerkvist
In this paper we are interested in the fine-grained complexity of deciding whether there is a homomorphism from an input graph to a fixed graph (the -Coloring problem).…
Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning
Leif Eriksson, Victor Lagerkvist
Allen's interval algebra is one of the most well-known calculi in qualitative temporal reasoning with numerous applications in artificial intelligence. Recently, there has been a s…
A Fast Algorithm for Consistency Checking Partially Ordered Time
Leif Eriksson, Victor Lagerkvist
Partially ordered models of time occur naturally in applications where agents or processes cannot perfectly communicate with each other, and can be traced back to the seminal work…
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…
Component twin-width as a parameter for BINARY-CSP and its semiring generalisations
Ambroise Baril, Miguel Couceiro, Victor Lagerkvist
We investigate the fine-grained and the parameterized complexity of several generalizations of binary constraint satisfaction problems (BINARY-CSPs), that subsume variants of graph…
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…