Improved Algorithms for Allen's Interval Algebra: a Dynamic Programming Approach

1 Introduction

Allen's interval algebra is an influential formalism within qualitative reasoning where the basic domain elements are intervals on the real line. For example, we can say that x precedes y, or that x overlaps y. These relationships are typically represented by 13 pairwise disjoint and jointly exhaustive basic relations and one can then express more complicated relationships between intervals by taking unions of the 13 basic relations. Allen's interval algebra has seen numerous applications within artificial intelligence and related areas, e.g., in planning [Allen and Koomen, 1983; Dorn, 1995; Mudrov´a and Hawes, 2015; Pelavin and Allen, 1987], natural language processing [Denis and Muller, 2011; Song and Cohen, 1988], and molecular biology [Golumbic and Shamir, 1993]. While deciding consistency of a graph of interval constraints, the network consistency problem, over the 13 basic relations is tractable, the problem is well-known to be NP-complete once unions of the basic relations are allowed [Allen, 1983].

Despite this, significant effort has been devoted towards solving real-world instances of the problem, using a wide array of different techniques [Nebel, 1997; Huang et al., 2013; Thornton et al., 2004; Pham et al., 2008; Sioutis and Janhunen, 2019]. Unfortunately, these methods are not sufficient to guarantee improved worst-case complexity, and little is thus known concerning fine-grained complexity. As remarked, the consistency problem is NP-complete, but recent progress in parameterised and fine-grained complexity suggests that NPhardness is a starting point, rather than the end goal. Hence, we are interested in bounding the running time required to solve the problem from above, by constructing improved algorithms (upper bounds), and below, by considering size-preserving reductions from problems where breaking a particular bound is deemed unlikely (lower bounds). Thus, taking an expected superpolynomial running time into account, what is the smallest c > 1 such that the network consistency problem for Allen's interval algebra is solvable in O(cn ) time, where n denotes the number of intervals? Or is it even feasible to expect a singleexponential running time, or would that contradict any existing results or conjectures? Crucially, questions asking for sharp upper and lower bounds cannot be answered by analysing existing methods, which to the best of our knowledge do not give any improved worst-case figures, but require novel and previously unexplored algorithms.

Before attacking these questions let us first remark that the network consistency problem for Allen's interval algebra can be seen as a special case of an infinite-domain constraint satisfaction problem (CSP). We view a CSP instance as a set of atomic constraints over a predetermined domain, and wants to know whether all variables can be assigned values without contradicting any constraint. Furthermore, it is common to restrict the constraints that may occur by parameterising the problem by a constraint language, and the resulting problem is then written as CSP(Γ). Then the network consistency problem for Allen's interval algebra is nothing else than CSP(A) where A is the set of relations obtained by closing the 13 basic relations in Allen's algebra under union. A related problem is the temporal CSP problem where each relation is first-order definable over (Q;<), and we write Γ(n) < for the set of all temporal relations of arity n ≥ 1.

It is then known that CSP(A) is not solvable in subexponential time, i.e., in 2o(n) time, unless 3-SAT is solvable in subexponential time [Jonsson and Lagerkvist, 2018]. The latter statement is in complexity theory known as the exponentialtime hypothesis (ETH) [Impagliazzo and Paturi, 2001] and is a popular conjecture for proving superpolynomial lower bounds. Let us also remark that CSP(A) can be brute forced by enumerating all possible assignments from pairs of variables to the set of basic relations. This results in a 2O(n2 ) algorithm, suggesting that there is plenty of room for improvement. Indeed, the problem can be solved in O∗ ((2n)2n ) (i.e., in 2O(n log n) ) time by translating each interval constraint to a temporal constraint in Γ(4) < (over the start- and endpoints of the intervals) and the resulting problem can be solved by enumerating all possible orderings among the variables [Jonsson and Lagerkvist, 2017]. However, there is still a large gap between this bound and 2o(n) , suggesting that at least one of the bounds can be improved further. Interestingly, CSP(Γ(4) < ) cannot in general be solved in 2o(n logn) time unless the (randomised) ETH is false [Jonsson and Lagerkvist, 2018], showing that this approach has its limits. Another optimistic development is the recent algorithm for CSP(A) restricted to unit intervals, which solves the problem in 2O(n log logn) time [Dabrowski et al., 2020]. Unfortunately, generalising the unit case to the full problem in a manner that yields an improved algorithm appears difficult.

After properly defining the relevant fundamental notions (Section 2) we turn to the problem of constructing improved algorithms for CSP(A). We consider two different approaches. First, in Section 3 we consider a novel approach of translating interval constraints to temporal constraints of arity at most 3, based on the idea of first fixing an order on the start points of the intervals, and then carefully translating each interval constraint to a constraint over a relation in Γ(3) < . Naturally, this only results in an improved algorithm if CSP(Γ(3) < ) admits an improved algorithm, and given the aforementioned 2o(n log n) lower bound for CSP(Γ(4) < ), it may appear doubtful that this is achievable. However, contrary to intuition, we manage to construct an O∗ (3n ) time algorithm for CSP(Γ(3) < ) based on dynamic programming (here, and in the sequel, we use the notation O∗ (·) to suppress polynomial factors). Dynamic programming is an influential design principle and has e.g. been used to obtain improved exponential-time algorithms for the Knapsack Problem [Andonov et al., 2000], the k-coloring problem [Bj¨orklund et al., 2009], and for the channel assignment problem with limited k channel distance [McDiarmid, 2003], but has to the best of our knowledge, not been applied to CSPs of this type before. We also give a conditional lower bound for CSP(Γ(3) < ) and show that it cannot be solved in O(cn ) time for any c < 2 unless k-coloring, for each k ≥ 1, is solvable in O(cn ) time. This matches the best concrete lower bound for CSP(A) [Jonsson and Lagerkvist, 2017], making it likely that even faster algorithms should target CSP(A) directly, rather than being based on reductions to a temporal CSP. In Section 4 we use this insight and attack the full CSP(A) problem directly, and obtain an O∗ ((1.0615n)n ) time algorithm utilising dynamic programming. This algorithm uses the fact that if we once know the exact relations of one interval compared to all others and know that these are all allowed relations, we from that point onward only need to remember that said interval has passed. Compared to previously mentioned O∗ ((cn)2n ) algorithms, this is a significant improvement, as our algorithm is the first yielding a linear expression in the base of the exponent, compared to a quadratic one. Interestingly, this algorithm can be adapted to give an O∗ (2dn (0.5307n)(2d-1)n ) time algorithm for the d-dimensional box algebra by reducing the dimension down to one, and then using the improved algorithm for CSP(A). To the best of our knowledge, this is the first explicit upper bound for the d-dimensional box algebra, which naturally raises the question of whether even faster algorithms can be obtained by targeting the box algebra directly, rather than going the route via CSP(A). We discuss this and other open questions in Section 6.

In summary, we not only succeed in strengthening upper bounds for CSP(A) and related problems, but also show that dynamic programming appears to be a generally usable method for constructing algorithms with theoretical worst-case guarantees for infinite-domain CSPs.

2 Preliminaries

We begin by defining the constraint satisfaction problem over a set of relations Γ (CSP(Γ)).

Definition 1. Let Γ be a set of finitary relations defined on a set D of values. The constraint satisfaction problem over Γ (CSP(Γ)) is defined as follows:

INSTANCE: a tuple (V,C), where V is a set of variables and C a set of constraints of the form R(v1, . . . , vt), where t is the arity of R ∈ Γ and v1, . . . , vt ∈ V .

QUESTION: is there a function f : V → D such that (f(v1), . . . , f(vt)) ∈ R for every R(v1, . . . , vt) ∈ C?

The set Γ is referred to as a constraint language, while the function f is a function satisfying an instance I, or simply a model for I. Observe that Γ or D may be infinite. Given an instance I of CSP(Γ), we let ||I|| denote the number of bits required to represent I. Our predominant way of defining useful constraint languages is to first fix a relational structure R = (D;R1, . . . ,Rm) of basic relations and then consider first-order reducts of R, i.e., sets of relations where each relation is defined as the set of models of a first-order formula over R (with equality).

Definition 2. A temporal constraint language is a first-order reduct of (Q;<).

In addition, we write Γ(k) < for the set of all temporal relations of arity k ≥ 1, use = in infix notation for equality, and write > for the converse of <. It is then well-known that CSP(Γ(2) < ) is tractable but that CSP(Γ(k) < ) is NP-hard for every k ≥ 3 [Bodirsky and K´ara, 2010]. Furthermore, note that an instance (V, C) of any temporal problem CSP(Γ) can always be solved in O∗ (|V ||V | ) time by enumerating functions from V to {1, . . . , |V |}. This observation can be generalised as follows.

Definition 3. A finite sequence of non-empty finite sets (S1, . . . , Sℓ) is an ordered partition of a set S if S1, . . . , Sℓ

is a partitioning of S. The ranking function r is the function r : S → {1, . . . , ℓ} such that r(x) = i for every x ∈ Si and every i ∈ {1, . . . , ℓ}.

For simplicity we will denote r(x) ⊙ r(y) as x ⊙r y when ⊙ ∈ {<, =, >}. Given any function f : S → X, where X is totally ordered, f defines an ordered partition on S as well as a ranking function r such that u⊙r v if and only if f(u) ⊙ f(v) for all u, v ∈ S and ⊙ ∈ {<, =, >}.

The total number of different ordered partition of a set containing n elements is counted by the n'th Ordered Bell Number (OBN(n)) (also known as the n'th Fubini number). This number OBN(n) is closely approximated by (n!/2)(log2 e)n+1 , or roughly (0.5307n)n · poly(n) after applying Sterling's approximation of n!.

Lemma 4. A model f to an arbitrary temporal CSP(Γ) instance I = (V, C) implies the existence of an ordered partition S = (S1, . . . , Sℓ) over V with ranking function r, such that x ⊙r y if and only if x ⊙f y for all x, y ∈ V .

Proof. Given f : V → X, take the ordered partition (α1, . . . , αℓ), where αi = {xj} for every xj ∈ X. Define r as r : V → {1, . . . , ℓ} such that r(v) = i if and only if f(v) ∈ αi, and define S = (S1, . . . , Sℓ) as the ordered partition having r as ranking function. If x⊙f y then x⊙r y must now be true, and vice versa.

We close this section by defining Allen's interval algebra. Here, the underlying domain consists of intervals on the real line, and we consider the 13 binary relations as described by Table 1. We let A be the constraint language obtained by closing these 13 basic relations under union, and observe that CSP(A) is a reformulation of the network consistency problem for Allen's interval algebra.

Strictly speaking, A is not a temporal language, but recall from Section 1 that if we treat every interval x as a pair of startand end-points (x-, x+), any CSP(A) instance can trivially be transformed to an equisatisfiable CSP(Γ(4) < )-instance. To simplify statements about start- and end-points we introduce the following two sets: V - = {x- | (x-, x+) ∈ V }, and similarly V + = {x+ | (x-, x+) ∈ V }. Note that x- < x+ trivially holds for every interval x and that Lemma 4 is also valid with respect to ordered partitions over V - ∪ V +.

3 An O∗ (3n) Algorithm for CSP(Γ(3) < )

We begin by constructing an improved algorithm for CSP(Γ(3) < ), i.e., the CSP problemwith temporal constraints of arity 3. As we will see, this algorithm can be used to obtain an improved algorithm for CSP(A), although its running time turns out to be worse than the specialised CSP(A) algorithm presented in Section 4.

Note that Γ(3) < is a symmetric constraint language in the following sense: for every relation R ∈ Γ(3) < and permutation π: {1, 2, 3} → {1, 2, 3} there exists R′ ∈ Γ(3) < such that a constraint R(x1, x2, x3) holds if and only if R′ (xπ(1), xπ(2), xπ(3)) holds. We will later make use of this symmetry to simplify our notation when proving correctness. Furthermore, recall that Lemma 4 tells us that any solution to a CSP(Γ(3) < ) instance (V,C) directly defines an ordered partition over V .

We proceed by describing our dynamic programming inspired algorithm, using the following notion of records. To avoid some tedious situations, we will from now on step away from the formal definition of an ordered partition by allowing the sequences to contain zero to three empty sets. This will have a polynomial increase in the number of possible ordered partitions, which we can safely ignore.

Definition 5. A record for a CSP(Γ(3) < ) instance (V,C) is an ordered partition (V<, V=, V>) of V , with some ranking function r, such that for every u ∈ V<, every v ∈ V>, and for all x, y, z ∈ V=, every constraint c(i, j, k) ∈ C with i, j, k ∈ {x, y, z, u, v} evaluates to true for r.

Algorithm 1 DP algorithm for CSP(Γ(3) < ).

1: function 3-ARITY-SOLVER(I = (V,C)) 2: S ← {(∅, ∅, V )} 3: for each record (V<, ∅, V>) ∈ S do 4: if V> = ∅ then 5: return T rue 6: end if 7: for each V= ⊆ V> do 8: if (V<, V=, V> \ V=) is a record then 9: S = S ∪ {(V< ∪ V=, ∅, V> \ V=)} 10: end if 11: end for 12: end for 13: return F alse 14: end function

Our algorithm for CSP(Γ(3) < ) is presented in Algorithm 1. The basic idea is to inductively build records by moving subsets from V> to V< via the set V=, while not contradicting any constraints in the instance.

Theorem 6. Algorithm 1 is correct and has an upper bound on runtime complexity of O∗ (3n ).

Proof. Given a yes-instance I = (V,C), we know from Lemma 4 that there exists some ordered partition s = (S1, . . . , Sℓ) with ranking function r, satisfying I. In this case, the algorithm can in every iteration 1 ≤ i ≤ ℓ choose V= to equal Si since this always results in a new record, and since s = (S1, . . . , Sℓ) is an (ordered) partition, we in the last iteration reach the case when V> = ∅ and return 'True'. Hence, Algorithm 1 answers 'True' if I is a yes-instance.

In the other direction, if Algorithm 1 answers 'True', there exists a sequence of records (constructed in line 8) (S1, . . . , Sℓ) with Si = (V<,i, V=,i, V>,i) and such that V<,i+1 = V<,i ∪ V=,i, ∅ ̸= V=,i+1 ⊆ V>,i, V>,i+1 = V>,i \ V=,i+1 for all 1 ≤ i < ℓ, V>,1 = V and V>,ℓ = ∅. Let f be the ranking function for (V=,1, . . . , V=,ℓ). Now, u <f v only if u <r v for r for some Si, and u =f v only if u =r v for r for all Si. For every triple x, y, z ∈ V there will be a record Si such that one of the following, or a symmetrical case, holds:

• x ∈ V<,i, y ∈ V=,i and z ∈ V>,i,
• x, y ∈ V=,i and z ∈ V>,i,
• x ∈ V<,i and y, z ∈ V=,i, or
• x, y, z ∈ V=,i.

Since Si is a record, any constraint c(x, y, z) (recall that Γ(3) < is symmetric) must evaluate to true for r for Si, and hence for f, and since this is true for all x, y, z ∈ V , every constraint in C must evaluate to true for f. Hence, f is a model of I, meaning that I is a 'yes'-instance whenever Algorithm 1 returns 'True'.

For the complexity, every variable in V can be placed in at most one of the three sets V<, V= and V>, at a time, which creates 3n possible combinations. Evaluating related constraints in C can be done in poly(||I||) time, and hence the final upper bound is O∗ (3n ).

Let us now see how Algorithm 1 can be used to obtain an improved algorithm for CSP(A). Here, the basic idea is to enumerate partial orders over the start-points V -, and given such an order we can then simplify the instance and solve it as a CSP(Γ(3) < ) instance. However, since we in Section 4 investigate a better, more direct method, we only provide a proof sketch of the main ideas.

Proof. (Sketch) Enumerate all ordered partitions for V -. For each ordered partition, all constraints in C can be transformed to Γ(3) < constraints and this give a new instance I3 that also enforces the ordered partition given. The exact input-output mapping of this transform can be calculated by combining the 13 basic relations for A with the three possible relations between related start-points. These combinations then show if a relation is directly false and if not, what the relations are still needed between x+, y+ and either x- or y-, to make the original interval relation true. Take the constraint ((x < y) ∨ (x o y) ∨ (x f y)) together with an ordered partition such that x- < y- as an example. This would yield the constraint (x+ < y- ∨ (y- < x+ ∧ x+ < y+) ∨ false)

after the transform. Our new instance I3 can then be solved with Algorithm 1. Due how the transform works, any ordered partition solving I3 would now also solve I.

The complexity is given by the product of the number ordered partitions OBN(n) and the cost for solving I3 using Algorithm 1. As the variables in V - must follow the same ordering as in the ordered partition used for the transform, the number of possible records are reduced from 3|V -|+|V +| to less than 3|V +| (2|V -| + 1), with some very minor modifications to the algorithm.

Naturally, an even faster algorithm for CSP(Γ(3) < ) could improve this even further, making it interesting to investigate how far we could push this bound. To this aim, consider the following reduction from the k-coloring problem (kCP): given a graph (V, E) we begin by introducing k fresh variables {c1, . . . , ck} and the constraints (c1 < c2), . . . , (ck-1 < ck). For every vertex xi ∈ V we then introduce the constraints (c1 < xi ∨ c1 = xi) ∪ (ck > xi ∨ ck = xi) and ⋃k-1 j=1 (cj > xi ∨ cj = xi ∨ cj+1 = xi ∨ ck+1 < xi), ensuring that every xi is equal to one cj. Last, for each edge (x, y) ∈ E we introduce a constraint (x < y ∨ x > y). It is easy to see that this reduction is correct, and put together, an O(cn ) time algorithm for CSP(Γ(3) < ) for c < 2 would then imply an O(cn ) time algorithm for kCP for every k > 0, and would thus beat the currently leading O∗ (2n ) time algorithm by Bj¨orklund and Husfeldt [2009].

4 Allen's Interval Algebra

We now present an O∗ ((1.0615n)n ) algorithm for CSP(A), and thus beat the O∗ ((1.5922n)n ) algorithm from Section 3 by a substantial margin. Similar to Γ(3) < , A is symmetric in the following sense: for every R ∈ A there exists R′ ∈ A such that a constraint R(x1, x2) holds if and only if R′ (x2, x1) holds. This simplifies our notations when talking about individual constraints, as there is no need to have different cases for R(x1, x2) and R′ (x2, x1). Recall from Lemma 4, and the subsequent remark, that any solution to a CSP(A) instance (V, C) directly defines an ordered partition over V - ∪ V +. We begin by defining the analogous notion of a record.

Definition 8. A record for a CSP(A) instance (V,C) is a tuple (Vok, V1, . . . , Vℓ, V>) such that

1. (V1, . . . , Vℓ, V>) is an ordered partitioning of U ⊆ V - ∪ V + with some ranking function r,
2. x- <r x+ for all x-, x+ ∈ U,
3. x- ∈ Vok if and only if x+ ∈ Vok, and
4. all constraints c(x, y) ∈ C such that x+ ∈ Vℓ and y-, y+ ∈ V1 ∪ . . . ∪ Vℓ ∪ V> evaluate to true for r.

We will assume that if we create a tuple (Vok, V1, . . . , Vℓ, V>) where some set Vi, 1 ≤ i ≤ ℓ is empty, that we instead use the tuple (Vok, V1, . . . , Vi-1, Vi+1, . . . , Vℓ, V>), i.e. any empty sets out of Vi, 1 ≤ i ≤ ℓ are simply ignored. This assumption simplifies our discussion of tuples and records by hiding unnecessary complications that have no impact on any results.

Ignoring empty sets in this manner is often needed for (V1, . . . , Vℓ, V>) to be an ordered partition.

The point of records is to give us full knowledge of any start- or end-point in Vi, 1 ≤ 1 ≤ ℓ, while simultaneously allowing us to maintain minimal knowledge about variables we have already made sure are positioned such that any related constraints are satisfied. Similarly, records also provides information about the start- and end-points we have yet to place. Our algorithmic approach is now to build tuples inductively from previous records, and to check if these tuples are records. See Algorithm 2 for a full description. The main idea is that once an interval has had both start- and end-point placed, and we have made sure that all constraint that this interval was part of are satisfied, it does no longer matter exactly where the interval was placed, we can safely remove the interval from the ordered partition, and thus reduce the amount of information that needs to be stored. The algorithm thus keeps track of the relations between all partially placed intervals, while ignoring the positions of all already placed, and compared, ones. For each end-point we are currently placing at line 8, we now know the relation to all other unplaced, or partially placed, intervals. For every interval placed before the ones we are currently placing, we have already passed through the same check, and can hence guarantee the any constraints containing at least one of those intervals have already been satisfied.

Algorithm 2 DP algorithm for CSP(A).

1: function DP-IA-SOLVER(I = (V,C)) 2: Let S ← {(∅, V - ∪ V +)} 3: for each record (Vok, V1, . . . , Vℓ, V>) ∈ S do 4: if V> = ∅ then 5: return 'True' 6: end if 7: for each set v ⊆ V> such that either x- ∈ v and x+ ̸∈ v, or x+ ∈ v and x- ̸∈ (V> ∪ v) do 8: if (Vok, V1, . . . , Vℓ, v, V> \ v) is a record then 9: Let t ← {x-, x+ | x+ ∈ v ∩ V + and x- ∈ (V1 ∪ . . . ∪ Vℓ) ∩ V -} 10: S ← S ∪ (Vok ∪ t, V1 \ t, . . . , Vℓ \ t, v \ t, V> \ v) 11: end if 12: end for 13: end for 14: return 'False' 15: end function

Proof. If I is a yes-instance, we know from Lemma 4 that there exists some ordered partition (S1, . . . , Sγ) with ranking function r satisfying I. Choosing v, at Line 7, such that v = Si when we have a record (Vok, V1, . . . , Vi-1, V>) with Vj ⊆ Sj for all 1 ≤ j ≤ i - 1 and V> = Si∪. . .∪Sℓ, will construct the new record (Vok, V1, . . . , Vi-1, v, V> \ v), at Line 8. Specifically the ordered partition (Vok, V1, . . . , Vi-1, v, V> \ v) with ranking function f, will always be such that x± ⊙f y± if x± ⊙r y±, for all x± ∈ v and y± ∈ (V + ∪ V -), and also for all x± ∈ V1 ∪ . . . ∪ Vi-1 ∪ v, and y± ∈ (V + ∪ V -) \ Vok. Hence, the ranking functions agree for all cases where at least one variable is in V1 ∪. . .∪Vi-1 ∪v. Since the algorithm does not move pairs (x-, x+) to Vok until x+ ∈ v, i.e. x- ∈ Vj for some j until x+ ∈ v occurs, x+ ⊙f z if and only if x+ ⊙r z for all z ∈ (V - ∪ V +), and similarly for x-. Given the definition of r, all constraints in C evaluates to true for r, so all constraints c(x, y) with y+, y- ∈ (V - ∪V +) \ Vok, will evaluate to true for f, too. Since all intervals in x ∈ V will have x+ ∈ v at one point when constructing records in this manner, every constraint in C evaluate to true for some f. Hence, a record where V> = ∅ will be reached, and the algorithm will return 'True'.

If Algorithm 2 returns 'True', there exists a sequence of records Sseq = (S1, . . . , Sℓ), constructed at Line 8, going from (∅, V - ∪ V +) to some (Vend, . . . , ∅). Let vseq = (v1, . . . , vℓ) with ranking function r, be the sequence of the v sets chosen at Line 7 corresponding to Sseq. For any pair of intervals x, y ∈ V with x+ ≤r y+, we will have a record s = (Vok, V1, . . . , v, V>) ∈ Sseq with x+ ∈ v and y+ ∈ (v ∪ V>). Let f be the ranking function for (V1, . . . , v, V>), any constraint c(x, y) ∈ C will evaluate to true for f , since s is a record. For all z, w ∈ V1∪. . .∪v∪{y+} then z ⊙f w implies z ⊙r w given the ordering we choose our v sets. Since this is true for any pair x, y ∈ V , r is a model for I. Hence, Algorithm 2 returns 'True' if and only if I is a yes-instance.

Lemma 10. Algorithm 2 has an upper bound on run time complexity of O∗ (2nOBN(n)) or O∗ ((1.0615n)n ) for an nvariable CSP(A) instance I = (V, C).

Proof. Checking whether a tuple is a record in line 8 is obviously polynomial. The size of V1 ∪ . . . ∪ Vℓ in a record stored in S, can never grow bigger than n, as it can only contain subsets of V -. There are ( nm) ways to select m variables out of V - for V1 ∪ . . . ∪ Vℓ, and then OBN(m) different ordered partitions of those m variables. The remaining n-m variables from V - can either be placed into Vok or into V>, in 2n-m different ways. Similarly, the m variables in V + bound to the m chosen variables from V -, can be placed in either v (always at the very end of the ordered partition, so no extra ordering cost for these), or in V>, giving another 2m. This gives the equation ∑nm=0 ( nm)OBN(m)2m. Simplifying this, and ignoring polynomial factors, gives

which concludes the proof.

5 Higher Dimensions Algebra

The d-dimensional block algebra is a well-known extension of the interval algebra where the basic objects are d-dimensional boxes, related by interval constraints over the respective dimensions [Dylla et al., 2017].

Definition 11. The d-dimensional block algebra (Ad ) is a constraint language of arity two, where each variable represents a set of d independent intervals X = (X1, ...,Xd). Each basic relation is as a set of d relations from A, one over each dimension, such that two different dimensions are never compared.

For example, the A2 relation X <,= Y means that X precedes Y in the first dimension, and equals Y in the second. While literature specifically about Ad becomes more sparse for larger values of d, using A2 to describe relations in the plane is not unheard of, e.g. [Papadias and Theodoridis, 1997; Zhang and Renz, 2014; Liu et al., 2009]. Intuitively, we can also see how A3 and A4 can be used for relations in a threedimensional space, or in a three-dimensional space together with a time dimension.

Inspired by the improved algorithm for CSP(A) from Section 4 we now turn to the problem of constructing an improved algorithm for CSP(Ad ) for every d ≥ 2. This problem can be brute forced by enumerating all possible orderings over the start- and end-points in the induced intervals, but to the best of our knowledge no faster algorithm has been detailed in the literature.

For CSP(Ad ) we will treat the variables in V as tuples containing one pair of start- and end-points for each dimension, i.e. x = (x-1 , x+1 , ..., x-d , x+d ) ∈ V . In addition, we extend the sets V + and V - to also contain the numbering of the dimension, i.e., let V - i = {x-i | (x-1 , x+1 , ..., x-d , x+d ) ∈ V }, V + i = {x+i | (x-1 , x+1 , ..., x-d , x+d ) ∈ V }, 0 < i ≤ d. Then, similar to how a solution to a CSP(A) instances defines an ordered partition over V - ∪ V +, a solution to a CSP(Ad ) instance defines d ordered partitions, one for each pair V - i ∪ V + i , 0 < i ≤ d. Our idea is then to enumerate all ordered partitions for all dimensions but one, and then solve the remaining instance as a CSP(A) instance. If the dimensions is d ≤ 1, this leads to a complexity of O∗ (2dnOBN(n)2d-1 ) using Algorithm 2 to solve the constructed CSP(A) instances.

Theorem 12. CSP(Ad ) is solvable in O∗ (2dnOBN(n)2d-1 ) time.

Proof. While d > 1, we enumerate over each ordered partitions over V - d ∪ V + d such that x- < x+ is true for all x ∈ V . For each such ordered partition we can, as all relations in that dimension are known, transform I to a new CSP(Ad-1 ) instance Id-1. We then repeat this recursively until d = 1 and then solve I1 using Algorithm 2. Hence, if Algorithm 2 returns 'True' for some I1 we have a set of d ordered partitions that satisfies I. Similarly, since we enumerate all possible combinations of ordered partitions until we reach I1, and since we know from Lemma 9 that Algorithm 2 is correct, it is possible to find a combination of ordered partitions satisfying I if I is a yes-instance.

For the complexity, there are OBN(2n)d-1 ordered partitions over V - i ∪ V + i for 1 < i ≤ d. However, only one in 2(d-1)n of these ordered partitions will obey x-i < x+i for all xi ∈ V and 1 < i ≤ d. Since the complexity of Algorithm 2 is in O∗ (2nOBN(n)) (Lemma 10) we obtain a run time of O∗ (2dnOBN(n)2d-1 ) or O∗ (2dn (0.5307n)(2d-1)n ) after a few simplifications.

6 Discussion and Conclusion

We studied the fine-grained complexity of temporal CSPs, with a particular focus on Allen's interval algebra, where we managed to obtain an O∗ ((1.0615n)n time algorithm. As remarked, this is a vast improvement over the 2O(n logn) time algorithm by Jonsson and Lagerkvist [2017]. We also extended the algorithm to yield an improved upper bound for the d-dimensional block algebra which is substantially faster than the naive enumeration algorithm. Importantly, we demonstrated that dynamic programming appears to be a generally usable method for improved algorithms of qualitative reasoning problems. Let us now briefly discuss a few potential directions for future research.

CSP(A) in single-exponential time? The holy grail in exponential-time algorithms is to obtain single-exponential time algorithms of the form O∗ (cn ) for some constant c > 1. Thus, can CSP(A) be solved in single-exponential time? If this appears insurmountable, might it then be possible to prove stronger lower bounds than an expected non-subexponential running time [Jonsson and Lagerkvist, 2018], assuming either the exponential-time hypothesis or its stronger variant?

CSPs over partial orders. CSP(A) is a special case of a broader class of CSPs, namely constraint languages consisting of binary, pairwise disjoint and jointly exhaustive relations containing a strict partial order satisfying certain additional properties [Jonsson and Lagerkvist, 2018]. For example, the region connection calculus is also included in this class. Can our dynamic programming algorithms be adapted to problems of this form, and might it even be possible to find a uniform algorithmwhich solves all problems in this class faster than the naive enumeration algorithm? Even more ambitiously, does there exist an NP-hard problem in this class which is solvable in single-exponential time?

The case for higher dimensions. Similar to how Algorithm 2 solves CSP(A) directly, rather than via temporal constraints, there is an extension of Algorithm 2 for solving higher dimensions directly, without having to fixate all but one dimensions. This can be done by extending Definition 8 to contain d-ordered partitions and by not moving variables from the partitions to the Vok set until every part of a d-dimensional variable have been fixed in the partitions. However, this gives a O∗ ((d2d+ 1d ( 2d-1 2d )2d-1 )nOBN(n)2d-1 ) run time, and hence, unexpectedly, results in a worse bound than Theorem 12. Thus, does there exist a faster, direct algorithm for CSP(Ad )?

Acknowledgements

We thank Peter Jonsson for helpful discussions on the topic of the paper, and the anonymous reviewers for several insightful comments. The first author is partially supported by the National Graduate School in Computer Science (CUGS), Sweden. The second author is partially supported by the Swedish Research Council (VR) under grant 2019-03690.