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

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 surge of improvements in the fine-grained complexity of NP-hard reasoning tasks, improving the running time from the naive 2O(n2) to O^*((1.0615n)n), with even faster algorithms for unit intervals a bounded number of overlapping intervals (the O^*(·) notation suppresses polynomial factors). Despite these improvements the best known lower bound is still only 2o(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^*((fraccnlogn)n) for Allen's interval algebra. To demonstrate that the technique is applicable to more domains we apply it to a problem in qualitative spatial reasoning, the cardinal direction point algebra, and solve it in O^*((fraccnlogn)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 2O(n) time algorithms are unlikely.