13 papers
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
The non-redundancy (NRD) of a constraint satisfaction problem (CSP) is a combinatorial quantity closely tied to the behavior of CSPs in various computational models including their…
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…