# A Multivariate Complexity Analysis of Qualitative Reasoning Problems

arXiv: https://arxiv.org/abs/2209.15275 · HTML: https://mlsanity.com/paper/2209.15275/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 41 references that are in the map.
- First posted on arXiv 30 Sep 2022.

## Builds on (most cited first, 2 of 2)

- [Multivariate Fine-Grained Complexity of Longest Common Subsequence](https://mlsanity.com/paper/1803.00938/) (2018)
- [Solving Infinite-Domain CSPs Using the Patchwork Property](https://mlsanity.com/paper/2107.01428/) (2021)

## Built on by (most cited first, 2 of 2)

- [A Fast Algorithm for Consistency Checking Partially Ordered Time](https://mlsanity.com/paper/2305.15917/) (2023)
- [Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning](https://mlsanity.com/paper/2305.15950/) (2023)

## Abstract (arXiv)

Qualitative reasoning is an important subfield of artificial intelligence where one describes relationships with qualitative, rather than numerical, relations. Many such reasoning tasks, e.g., Allen's interval algebra, can be solved in 2O(n · log n) time, but single-exponential running times 2O(n) are currently far out of reach. In this paper we consider single-exponential algorithms via a multivariate analysis consisting of a fine-grained parameter n (e.g., the number of variables) and a coarse-grained parameter k expected to be relatively small. We introduce the classes FPE and XE of problems solvable in f(k) · 2O(n), respectively f(k)n, time, and prove several fundamental properties of these classes. We proceed by studying temporal reasoning problems and (1) show that the Partially Ordered Time problem of effective width k is solvable in 16kn time and is thus included in XE, and (2) that the network consistency problem for Allen's interval algebra with no interval overlapping with more than k others is solvable in (2nk)2k · 2n time and is included in FPE. Our multivariate approach is in no way limited to these to specific problems and may be a generally useful approach for obtaining single-exponential algorithms.