Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming

The region connection calculus with 5 or 8 basic relations (RCC-5/8) and Allen's interval algebra (IA) are two well-known NP-hard spatial-temporal qualitative reasoning problems. They are solvable in $2^{O(n \log n)}$ time, where $n$ is the number of variables, and IA is additionally known to be solvable in $o(n)^n$ time. However, no improvement over exhaustive enumeration is known for RCC, and if they are also solvable in single exponential time $2^{O(n)}$ is unknown. We investigate multiple avenues towards reaching such bounds. First, we show that branching on constraints is unlikely to yield a single exponential bound since there are too many non-redundant constraints. Concretely, we classify the maximum number of non-redundant constraints with respect to all basic relations in RCC and IA. Algorithmically, we make two significant contributions based on dynamic programming. The first algorithm runs in $4^n$ time and is applicable to a non-trivial, NP-hard fragment of IA, which includes the well-known interval graph sandwich problem (Golumbic and Shamir, 1993). For the richer RCC-8 problem we use a more sophisticated approach which asymptotically matches the $o(n)^n$ bound for IA.