# Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning

# Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning

## Leif Eriksson, Victor Lagerkvist

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence

Main Track. Pages 1919-1926.
https://doi.org/10.24963/ijcai.2023/213

Allen's interval algebra is one of the most well-known calculi in qualitative temporal reasoning with numerous applications in artificial intelligence. Very recently, there has been a surge of improvements in the fine-grained complexity of NP-hard reasoning tasks in this algebra, which has improved the running time from the naive 2^O(n^2) to O*((1.0615n)^n), and even faster algorithms are known for unit intervals and the case when we a bounded number of overlapping intervals.
Despite these improvements the best known lower bound is still only 2^o(n) under the exponential-time hypothesis and major improvements in either direction seemingly require fundamental advances in computational complexity.
In this paper we propose a novel framework for solving NP-hard qualitative reasoning problems which we refer to as dynamic programming with sublinear partitioning.
Using this technique we obtain a major improvement of O*((cn/log(n))^n) for Allen's interval algebra. To demonstrate that the technique is applicable to further problem domains we apply it to a problem in qualitative spatial reasoning, the cardinal direction calculus, and solve it in O*((cn/log(n))^(2n/3)) time. Hence, not only do we significantly advance the state-of-the-art for NP-hard qualitative reasoning problems, but obtain a novel algorithmic technique that is likely applicable to many problems where 2^O(n) time algorithms are unlikely.

Keywords:

Constraint Satisfaction and Optimization: CSO: Constraint satisfaction

Knowledge Representation and Reasoning: KRR: Qualitative, geometric, spatial, and temporal reasoning