6 papers
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{…
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…
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…
Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
Peter Jonsson, Victor Lagerkvist, Johannes Schmidt +1
Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jonsson et al. (SODA 2013) show that the…