---
title: "A Multivariate Complexity Analysis of Qualitative Reasoning Problems"
authors:
  - "Leif Eriksson"
  - "Victor Lagerkvist"
doi: "10.24963/ijcai.2022/251"
url: "https://ijcai.org/proceedings/2022/251"
pdf: "https://ijcai.org/proceedings/2022/0251.pdf"
venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence"
year: 2022
pages: "1804-1810"
track: "Main Track"
keywords:
  - "Constraint Satisfaction and Optimization: Constraint Satisfaction"
---

# A Multivariate Complexity Analysis of Qualitative Reasoning Problems

Leif Eriksson, Victor Lagerkvist

*Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 1804-1810. DOI: [10.24963/ijcai.2022/251](https://doi.org/10.24963/ijcai.2022/251)

## Abstract

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 2^O(n*log n) time, but single-exponential running times 2^O(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)*2^O(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 16^{kn} 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}*2^n 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.

## Full text

## 1 Introduction

Qualitative reasoning is an important formalism in artificial intelligence where the objective is to reason about continuous properties given certain relations between the unknown entities, expressed qualitatively rather than quantitatively (e.g., numerically). Two important subfields are spatial reasoning, where basic objects e.g. may be regions in space defined in terms of other regions, and temporal reasoning, where one wishes to describe the relationship between time points, and more generally, between intervals of time points. Examples of the former include the REGION CONNECTION CALCULUS and the CARDINAL DIRECTION CALCULUS, and to exemplify the latter we may e.g. mention ALLEN'S INTERVAL ALGEBRA, the BRANCHING TIME problem, and the PARTIALLY ORDERED TIME problem. For many more examples and practical applications of these formalisms, cf. the survey by Dylla et al. [2017]. The classical complexity of qualitative reasoning is well understood: they are generally NP-hard but form non-trivial tractable fragments by restricting the types of basic relations. However, the tractable cases have limited strength, and in practice we therefore also need to solve NP-hard reasoning tasks. Hence, is there any hope of solving these intractable problems, or do we have to be contempt with heuristics? Here, modern complexity theory tells a more nuanced story than the classical theory, where NP-hardness is the beginning rather than the end. There are two prominent views:

1. Fine-grained complexity: for a fine-grained parameter n, e.g., the number of variables, how fast can the problem be solved, and are existing algorithms close to being optimal (given complexity theoretical assumptions such as the (strong) exponential-time hypothesis ((S)ETH))?
2. Parameterized complexity: for a coarse-grained parameter k, e.g., tree-width, which problems are fixedparameter tractable (FPT) - are in P if one is allowed unlimited computational resources (with respect to k) to preprocess the instance?

Crucially, n is expected to grow with the size of the instance while k is expected to stay small. Hence, fine-grained and parameterized complexity are not competing methods but tackle different aspects of intractability, with diverging algorithmic toolboxes. Unfortunately, neither approach seem fit for qualitative reasoning problems. On the one hand, they are solvable in 2O(n2 ) time or 2O(n·logn) time in certain cases [Jonsson and Lagerkvist, 2017], but we can currently only rule out subexponential 2o(n) algorithms under ETH [Jonsson et al., 2021]. On the other hand, despite the immense success of parameterized complexity, there is a lack of natural FPT algorithms for qualitative reasoning, and we are only aware of a handful of less surprising examples such as tree-width [Bodirsky and Dalmau, 2013; Dabrowski et al., 2021].

Hence, are we asking the right questions by attacking these problems with parameterized and fine-grained complexity, or are current attempts misguided? Could it be the case that they simply are too hard to admit natural FPT algorithms? Similarly, could it be the case that (e.g.) ALLEN'S INTERVAL ALGEBRA is not solvable in single-exponential time while still being fundamentally too different from 3-SAT to admit stronger lower bounds than 2o(n) ? In this article we bridge the gap between fine-grained and parameterized complexity and attack this question by a multivariate complexity analysis of single-exponential time solvability: which NP-hard qualitative reasoning problems admit single-exponential time algorithms (with respect to a fine-grained parameter n) once preprocessed with respect to a coarse-grained parameter k? This approach is a natural continuation of Bringmann & K¨unnemann [2018] who studied the complexity of the LONGEST COMMON SUBSEQUENCE problem in order to investigate which natural parameters could possibly break the SETH barrier. However, the exponential world of NP-hard qualitative reasoning problems is very different from the tractable LONGEST COMMON SUBSEQUENCE problem and requires new tools and techniques. Our paper has two main contributions. First, in Section 3 we initiate a systematic investigation of complexity classes taking both a coarse-grained parameter k and a fine-grained parameter n into consideration. We identify two natural classes: FPE, problems solvable in f(k) · 2O(n) time, and XE, problems solvable in f(k)n time. Naturally, FPE is more desirable due to the complete separation of the parameter n and k and should be viewed as the exponential analogue of FPT, while XE corresponds to the less desirable class XP where the two parameters are intertwined. Second, in Section 4 we begin the multivariate analysis of single-exponential time solvability by classifying parameterized problems as belonging to FPE, XE, or neither (under the ETH). We first consider the finite-domain constraint satisfaction problem (CSP) and manage to rule out inclusion in both FPE and XE under the ETH for several natural parameterizations. We then turn to two well-known problems from temporal reasoning: the PARTIALLY ORDERED TIME problem [Anger et al., 1999], which is the problem of determining whether there exists a partial order subjected to a set of constraints over a variable set, and ALLEN'S INTERVAL ALGEBRA [Allen, 1983], the problem of determining whether a set of 2-dimensional intervals described by 1-dimensional temporal constraints over the start- and end-points, is consistent or not. ALLEN'S INTERVAL ALGEBRA has seen applications in e.g. planning [Allen and Koomen, 1983; Dorn, 1995; Mudrov´a and Hawes, 2015], natural language processing [Denis and Muller, 2011; Song and Cohen, 1988], and molecular biology [Golumbic and Shamir, 1993], while the PARTIALLY ORDERED TIME problem occurs naturally in distributed systems where time is not totally ordered, cf. Lamport's classical interprocessor communication model [Lamport, 1986; Anger, 1989]. Both of these problems can be solved in 2O(n·logn) time by enumeration, and ALLEN'S INTERVAL ALGEBRA is additionally known to admit an improved O(1.0615nn ) algorithm [Eriksson and Lagerkvist, 2021]. For PARTIALLY ORDERED TIME we consider effective width as parameter, which in strength lies between the well-known properties of width and dimension. Here, we construct an XE-algorithm with a running time dominated by 16kn where k is the effective width of the partial order. The algorithm is non-trivial and attempts to construct a partial order of effective width k by guessing a suitable partition of the variable set and the ordering among all variables, which can be efficiently implemented via a recursive strategy making use of dynamic programming. For ALLEN'S INTERVAL ALGEBRA we define a parameter k based on the maximum number of overlapping intervals and construct a (2nk)2k · 2n time algorithm, and thus prove membership in FPE. Hence, for instances where k stays reasonably small our algorithm is effectively as good as a 2n -time algorithm, which is a major improvement over the aforementioned O(1.0615nn ) time algorithm. It is worth mentioning that both of these algorithms also solve the more involved problem of counting the number of solutions.

Our work opens up several directions for future research, which we describe in greater detail in Section 5. Most importantly, which parameterized problems in qualitative reasoning, and artificial intelligence as a whole, belong to FPE, and which belong to XE?

The proofs of statements marked with an asterisk (*) have been omitted due to space constraints.

## 2 Preliminaries

Throughout, let Σ be an alphabet, i.e., a finite set of symbols. For x ∈ Σ∗ we let |x| be its length.

Definition 1. A parameterized problem is a subset of Σ∗ × N where k ∈ N is called the parameter.

The goal of parameterized complexity is then to describe the complexity in terms of the parameter, and, ideally, design algorithms which decouples the parameter to |x|.

Definition 2. We introduce the following running times and the corresponding classes from parameterized complexity:

1. f(k) · |x|O(1) time by a deterministic algorithm (FPT),
2. |x|f(k) time by a deterministic algorithm (XP),

where f : N → N is a computable function.

FPT can be seen as the parameterized version of P where the parameter is completely decoupled from the rest of the instance via the factor f(k). The class XP, in comparison, still yields a polynomial-time algorithm for every fixed k but the dependency on k is much worse.

If a fine-grained parameter such as the number of variable n is used as parameter then the objective is typically to obtain precise upper and lower bounds on running times of the form f(n) · |x|O(1) , and the resulting field is sometimes called fine-grained complexity. If we let SE be the subclass of FPT allowing subexponential running times of the form 2o(n) · |x|O(1) then the conjecture that 3-SAT is not included in SE is known as the exponential-time hypothesis (ETH).

Before introducing the qualitative reasoning problems under consideration in this paper we introduce the more general class of constraint satisfaction problems (CSPs).

## CSP

Instance: I = (V, C) where V is a set of variables and C a set of constraints over a domain D.

Question: Does there exist a function f : V →D which satisfies all constraints, i.e., (f(x1), . . . , f(xm)) ∈ R for every R(x1, . . . , xm) ∈ C?

A set of relations Γ naturally induces a problem CSP(Γ) where constraints only uses relations from Γ. For a set B of relations of the same arity we write B∨= for the set of all relations that can be obtained by unions of the relations in B.

Definition 3. A pair (S,≤) is a partial order if ≤ is reflexive, asymmetric (∀x, y ∈ S, x ≤ y ⇒ not y ≤ x), and transitive.

If ⊙ ∈ {<,>, ||,=} and P = (S,≤P ) is a partial order then we write ⊙P for the relation induced by P: x <P y if x ≤P y and y ≤P x does not hold, conversely for >P , ||P if neither x ≤P y nor y ≤P x, and x =P y if x ≤P y and y ≤P x. We will differ between relations in P and the relations induced by P in the same manner, i.e. x ≤P y is a relation in P , while x <P y is a relation induced by P .

## PARTIALLY ORDERED TIME

Instance: A set of variables V and a set of binary constraints C where c ⊆ {<, >, ||, =} for each c(x, y) ∈ C. Question: Is there a partial order P = (S,≤) with |S| ≤ |V | and a function f : V → S such that for every constraint c(x, y) ∈ C, f(x) ⊙P f(y) for some ⊙ ∈ c?

For a PARTIALLY ORDERED TIME instance I = (V, C) and X ⊆ V we write I[X] = (X, CX) for the sub-instance where CX = {c(x, y) ∈ C | x, y ∈ X}. Similarly, if P = (S, ≤) is a partial order and S′ ⊆ S then we by P [S′ ] denote the partial order induced by P and S′ .

The second major problem analysed in the paper is ALLEN'S INTERVAL ALGEBRA: define a as the thirteen possible atomic relations between two intervals on the same line (see the technical appendix for precise definitions of these relations). The consistency problem for ALLEN'S INTERVAL ALGEBRA can then be seen as CSP(A) where A = a∨=, i.e., each constraint can be expressed as a union of basic constraints. We represent intervals as pairs of start- and end-points X = (x-, x+) such that x- < x+. In the same manner, for any CSP(A) (V,C) we introduce the two auxiliary sets V - = {x- | (x-, x+) ∈ V } and V + = {x+ | (x-, x+) ∈ V }.

## 3 Multivariate Complexity Classes

Our main interest are problems solvable in 2f(n) time for f ∈ O(n) (henceforth written 2O(n) ). This naturally leads to the following parameterized variant of the classical complexity class E, which is typically defined via the parameter |x|.

Definition 4. E is the class of parameterized problems solvable in 2O(n) · |x|O(1) time.

The choice of parameter n greatly influences the existence of a 2O(n) algorithm. For example, if we use the number of constraints m as the parameter then CSP(A) is in E via a trivial backtracking algorithm, but it is only known to be solvable in 2O(n·log n) time. Similarly, a cn · |x|O(1) algorithm for c < 2 for CNF-SAT would constitute a major break through in complexity theory, but if we instead use the number of clauses m as the complexity parameter then the problem can be solved in O(1.2226m) time [Chu et al., 2021].

Example 5. The TRAVELLING SALESMAN problem is trivially solvable in n!·|x|O(1) time but can be solved in 2n ·|x|O(1) time by the Held-Karp algorithm. Similarly, GRAPH COLORING can be solved in kn · |x|O(1) time, where k is the number of colors, or nn · |x|O(1) time if analyzed only by the number of vertices n, but can be solved in 2n · |x|O(1) time via an inclusion-exclusion based algorithm [Bj¨orklund et al., 2009].

For infinite-domain examples, let Γk be the set of all k-ary first-order definable relations over (Q;<) (temporal CSPs). Then CSP(Γ3 ) is solvable in 3n · |x|O(1) time [Eriksson and Lagerkvist, 2021] but CSP(Γ4 ) is not in E under the ETH [Jonsson and Lagerkvist, 2018]. In contrast, if ∆k is the set of all k-ary first-order definable relations over (N;=) (equality CSPs) then CSP(∆k ) is solvable in ( k(k-1) 2 )n · |x|O(1) time [Jonsson and Lagerkvist, 2020] and is thus in E.

Importantly, no NP-hard qualitative reasoning tasks are known to be solvable in single-exponential time, necessitating a multivariate analysis where the complexity is measured with respect to several parameters.

Definition 6. A multi-parameterized problem is a subset of Σ∗ ×Nc where n, k1, . . . , kc-1 ∈ N are called the parameters. A bi-parameterized problem is a multi-parameterized problem with only two parameters: n and k.

For simplicity we, given an instance (x, n, k) of a biparameterized problem, will always view the first parameter n as the fine-grained parameter, and the second parameter k as the coarse-grained parameter. Inspired by FPT and XP we then define the following bi-parameterized analogues.

Definition 7. We introduce the following two classes.

1. FPE: problems solvable in f(k) · 2O(n) · |x|O(1) time, and
2. XE: problems solvable in f(k)n · |x|O(1) time,

where f : N → N is a computable function.

Note that these running times are not symmetric with respect to the two parameters since we expect the parameter k to stay reasonably small, while n, naturally, grows rapidly with the size of the instance. Hence, the common trick in parameterized complexity to collapse two parameters into a single parameter n + k is not suitable for defining these classes. Additionally, it is possible to establish several fundamental properties of these classes and (1) derive FPE as a class of the form para-E using standard constructions in parameterised complexity, (2) define reductions preserving membership in these classes, and (3) prove that FPE can equivalently be defined via running times of the following form.

Theorem 8. (*) A bi-parameterized problem is in FPE if and only if it is solvable in nf(k) · 2O(n) · |x|O(1) time for computable f : N→N.

Example 9. The CSP problem is in XE if k is the size of the domain and n the number of variables but is not in FPE unless the ETH fails (see Theorem 10). For a less trivial XE example, consider the problem of finding a homomorphism between two graphs G and H over vertices VG and VH. If we let n be |VG|, and k be the tree-width of H, then the problem is solvable in (k + 3)n · |x|O(1) time, and if n = max{VG, VH} and k is the clique-width of H then it is solvable in (2k +1)n · |x|O(1) time [Fomin et al., 2007; Wahlstr¨om, 2011]. From Example 5, equality CSPs are in XE when parameterized by maximum arity while temporal CSPs are not in XE with the same parameterization. More generally, if B is a so-called partition scheme, then the CSP problem where constraints are formed by disjunctions of arity at most k, using relations from B, is in XE when parameterized by the maximum variable degree [Jonsson et al., 2021]. A nontrivial, related example can also be found in the CHANNEL ASSIGNMENT PROBLEM which is in XE when parameterized by the edge-length k of the input graph [McDiarmid, 2003].

Curiously, while XE-algorithms appear to be abundant in the literature, FPE-algorithms are much rarer and we are not aware of any non-trivial examples.

## 4 Parameterized Problems in FPE and XE

We now analyse FPE and XE in greater detail and begin in Section 4.1 by considering finite-domain CSPs with parameters such as domain size and degree. In Section 4.2 we consider the effective width of a partial order as a coarse-grained parameter for PARTIALLY ORDERED TIME, and construct a non-trivial XE-algorithm. Last, in Section 4.3, we use the maximum number of possible interval overlaps as a parameter for ALLEN'S INTERVAL ALGEBRA, resulting in the first non-trivial example of a problem in FPE.

## 4.1 Finite-Domain CSPs

For a finite-domain CSP instance (V, C) we consider the following parameters (ar(R) is the arity of a relation R).

1. dom((V,C)) = ⋃(d1,...,dar(R))∈R,R(x)∈C {d1, . . . , dar(R)},
2. max-arity((V, C)) = max{ar(R) | R(x) ∈ C},
3. max-degree((V,C)) = max{degree(x,C) | x ∈ V } where degree(x, C) = |{R(x) ∈ C | x occurs in x}|,
4. max-cardinality((V, C)) = max{|R| | R(x) ∈ C},

For each such parameter f we write p-f-CSP for the biparametrized problem obtained by letting the coarse-grained parameter k equal f((V, C)) and the fine-grained parameter n equal the number of variables |V | (for a CSP instance (V, C)).

Theorem 10. (*) Assume that the ETH is true. Then:

1. p-dom-CSP is in XE but not in FPE,
2. p-max-arity-CSP is not in XE,
3. p-max-degree-CSP is not in FPE, and
4. p-max-cardinality-CSP is in XE but not in FPE.

It may be interesting to note that all these bound are tight, with the possible exception of p-max-degree-CSP, where we currently do not know whether it is included in XE.

## 4.2 Partially Ordered Time

The first major temporal reasoning problem we consider is the PARTIALLY ORDERED TIME problem where we use a form of width as the coarse-grained parameter.

Definition 11. A partial order P = (S, ≤P ) is said to have effective width k if S can be partitioned into at most k + 2 disjoint subsets (S1, . . . , Sk, S<, S>) such that:

1. at least two of the sets (S1, . . . , Sk, S<, S>) are nonempty, unless all elements are equal,
2. for all x ∈ S< there is a Si such that for all y ∈ Si then x ≤P y and not y ≤P x,
3. for all x ∈ S> there is a Si such that for all y ∈ Si then x ≥P y and not y ≥P x,
4. for all pairs x ∈ S<, y ∈ S> with x ≤P y, then there is a Si such that for all z ∈ Si then x ≤P z ≤P y,
5. all partial orders P[S1], . . . , P[Sk], P[S<], P[S>] have effective width k, and
6. for every pair Si, Sj ∈ {S1, . . . , Sk}, i ̸= j, all x ∈ Si and all y ∈ Sj are incomparable in P .

The collection of sets S1, . . . , Sk is called the waist of P .

Effective width is a weaker constraint than width (the size of the largest anti-chain), but is likely a stronger condition than the dimension of a partial order, i.e., the least number of total orders whose intersection equals the partial order.

## PARTIALLY ORDERED TIME OF EFFECTIVE WIDTH k

Instance: A partially ordered time instance (V, C).

Parameters: n = |V |, k ∈ N.

Question: Is there a partial order P with effective width k

which satisfies the instance?

We introduce the following two definitions to simplify the notation in the forthcoming algorithm.

Definition 12. Let B(n, k) be the value of the k-th bit of the bit-string representing the integer n.

Definition 13. Given a binary relation ⊙, a variable x and a set V , we say that x⊙V if x⊙ v for all v ∈ V .

This notation easily extends to pairs of sets. The basic idea is then to recursively construct a partial order P of effective width k by enumerating all possible waists and relations between the other variables and said waist. This enumeration is then combined with dynamic programming to keep track of already solved subproblems. First, observe that each element not in a waist can (independently) be either < (or >) or incomparable to each of the k sets of said waist. If we are relating to two waists at once we then obtain 4k possibilities.

Theorem 14. Partially Ordered Time of effective width k is solvable in 16kn · |x|O(1) time, and is hence in XE.

Proof. For a PARTIALLY ORDERED TIME instance (V,C) of effective width k we define a recursive function X, taking as input 4k pairwise disjoint subsets of V , S1, . . . , S4k as follows. If only one Si ̸= ∅, check if the assumption that all variables of that set are equal is consistent with C. This can easily be done in polynomial time. If yes, the instance is accepted, otherwise we continue as follows. We introduce two temporary waists of size k: {T < 1 , . . . , T < k } and {T > 1 , . . . , T > k }. Assume that T < i <P Sj ⇔B(j, 2i -1) = 1 and T > i <P Sj ⇔B(j, 2i) = 1. Partition ⋃ Si into the new sets N W i for i ∈ {1, . . . , k}, and N < i , N > i for i ∈ {1, . . . , 4k }, such that no constraint is broken under the following assumptions:

1. if B(i, 2j) = 1 then N < i <P N W j and N > i <P T > j ,
2. if B(i, 2j -1) = 1 then T < j <P N < i and N W j <P N > i ,

3. all pairs N W i and N W j are incomparable if i ̸= j.

This means that for each i there is a j such that N W i ⊆ Sj, and since every variable not in a waist must relate to the waist, some sets must always be empty. For each partition, recursively check that I[N W i ], I[⋃ N < i ] and I[⋃ N > i ] are 'yes'- instances for all i (when they exist) under the assumptions just made. If one partition is found that is consistent with C and X (N < 1 , . . . ,N < 4k), X(N W 1 , ∅, . . . ), . . . , X(N W k , ∅, . . . ) and X (N > 1 , . . . ,N > 4k) all accept, then accept X(S1, . . . , S4k).

For | ⋃ Si| ≤ 1 the algorithm is clearly correct. Assume that the algorithm is correct for all | ⋃ Si| < n. Now, for correctness of | ⋃ Si| = n, we start with soundness. We bruteforce enumerate all partitions and reject a partition if there is any constraint not consistent with said partition. For every constraint c(x, y) ∈ C, there will at some point be a partition where x and y are not part of the same recursive call to X. At that point we will know the exact relation between x and y, and hence we can check if this relation is accepted by the constraint c(x, y). Hence, if we answer 'yes', all constraints will be satisfied. To see that we find an partial order, the question boils down to knowing transitivity holds correctly. Since we reject all partitions that breaks our assumptions, we will never accept x <P y if we have earlier assumed that z <P x and that y and z are incomparable. The same is true for the symmetric case when z <P x is assumed by some earlier partition and x <P y by the current partition. Also x ∈ N W i and y ∈ N W j would only be accepted it x being incomparable to y is accepted by our constraint c(x, y). Hence, these assumptions are enough to ensure that we actually obtain a partial order. For effective width we follow the definition and in each step make sure that: everything not part of the waist is related to some part of the waist, all parts of the waist are incomparable to every other part of the waist, and that all of I[⋃ N < i ], I[N W 1 ], . . . , I[⋃ N W k ], and I[⋃ N > i ] have effective width k. Hence, we will only answer 'yes' if we are given a 'yes'-instance. For completeness, assume there is some partial order PA of effective width k satisfying I. Since PA exists, the waist N W 1 , . . . ,N W k exists and we will find it and the correct partitions to give as inputs to the subproblems, when brute-force testing all possible partitions. Since the algorithm is assumed to be correct for every problem smaller than n, it must be correct (and thus complete) for these subproblems. The complexity analysis is straightforward but is omitted due to space constraints.

## 4.3 Allen's Interval Algebra

The second major qualitative reasoning problem we study is a variant of ALLEN'S INTERVAL ALGEBRA where we restrict the number of intervals any interval may overlap with.

Definition 15. We say that two intervals I and J overlap if there is a point x such that I - < x < I + and J - < x < J +.

## k-CSP(A)

Instance: A CSP(A) instance I = (V, C).

Parameters: n = |V |, k ∈ N.

Question: Is there a satisfying assignment where no interval

overlaps with k or more intervals?

We will prove that k-CSP(A) is solvable in roughly (2kn)2k · 2n time and space, and thus prove membership in FPE. Our algorithm makes use of a relationship between satisfying assignments and so-called ordered partitions.

Definition 16. 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, . . . , ℓ}. The number of unique ordered partitions for a set of size n is given by the Ordered Bell Number OBN(n) and is strictly less than the number of possible ways to arrange n items into n different sets if n > 1, nn .

It is known that CSP(A) over V is satisfiable if and only if there exists an ordered partition of V - ∪ V + and a ranking function r, such that, for any relation ⊙ ∈ {<,>,=}, r(x) ⊙ r(y) if and only if f(x) ⊙ f(y) for all x, y ∈ V - ∪ V + [Eriksson and Lagerkvist, 2021]. To simplify the notation we allow ordered partitions to (temporally) contain empty sets Si and we then assume that (S1, . . . , Si, . . . , Sℓ) = (S1, . . . , Si-1, Si+1, . . . , Sℓ). We will explicitly make sure this step is taken, but allowing this slight bending of the definition lets us avoid some unnecessarily complex steps.

Definition 17. Given a sequence (such as e.g. an ordered partition) (x1, . . . , xi) let the notation (x1 : xi) denote this sequence. Let (x1 : xi - xj) = (x1, . . . , xj-1, xj+1, . . . , xi), j ∈ {1, . . . , i}.

Theorem 18. k-CSP(A) is solvable in (2nk)2k · 2n · |x|O(1) time, and is hence in FPE.

Proof. The algorithm is similar to [Eriksson and Lagerkvist, 2021] and works by the following principle: by introducing intervals from smallest starting-point, to largest end-point, we only need to keep track of intervals already passed, current open intervals, how many other intervals these has already overlapped with, and intervals not yet opened. Given an kCSP(A) instance I = (V,C), for inputs V - 1 (a set), X = (X1 : Xi) (a partial order), v = (v1 : vi) (a collection of values) and V - 2 (a set) we then define a recurrence relation R(V - 1 ,X, v, V - 2 ) as follows:

- R(V - 1 , (X1 : Xi -Xj), (v1 : vi - vj), V - 2 ), if Xj = ∅,
- 0, if vj < 0 for any j ∈ {1, . . . , i},
- 1, if V - 1 = V -, and
- ∑x-⊆⋃ Xj,y⊆V - 2 f(V - 1 ,X, v, V - 2 , x-, y) otherwise.

If two cases are applicable for the same input, the first, as ordered here above, have the highest priority. Given x- and X = (X1 : Xi) define x+ = {x+j | (x-j , x+j ) ∈ V ∧ x-j ∈ x-} and X+ = {x+j | (x-j , x+j ) ∈ V ∧ x-j ∈ ⋃ Xl \ x-},

<!-- formula-not-decoded -->

<!-- formula-not-decoded -->

if and only if the assumptions (X1 : Xi, y ∪ x+) and u &lt; v for all u ∈ ⋃ Xj ∪ y ∪ x+, v ∈ V - 2 ∪ X+ is consistent with C. I.e. for any constraint c+(u, v) = c-(u, v) ∈ C (A is closed under symmetry, so the constraints are equal) with v- ∈ ⋃ Xj ∪ V - 2 and u+ ∈ x+ then the assumption satisfies c+(u, v). Otherwise f outputs 0.

Our algorithm for the decision problem is simply to check if R(∅, (), (), V -) &gt; 0. To see that this approach is sound we follow a sequence of R-recurrences from R(∅, (), (), V -) to R(V -, (), (), ∅) such that in each step we have that R &gt; 0. Take the ordered partitions that are part of this sequence, and merge them into a single ordered partition (Y1 : Yn) such that if x &lt; y in some (X1 : Xl, V - 2 ) for some R(V - 1 , (X1 : Xl), v, V - 2 ), then x &lt; y in (Y1 : Yn). Since R works by moving starting-points from the set V - 2 to X and then further to V - 1 , while keeping track of relevant previous intervals (Y1 : Yn) exists and is uniquely defined for each such sequence. The positions of the end-points in (Y1 : Yn) is implicit from the relation between x- and x+ in our definition of f. Let u- ∈ Yi-, u+ ∈ Yi+, u′- ∈ Yj- and u′+ ∈ Yj+. Assume i+ ≤ j+, then for each constraint c(u, u′ ) ∈ C in our sequence of R-recurrences, there is an R(V - 1 ,X, v, V - 2 ) followed by R(V ′- 1 ,X′ , v′ , V ′- 2 ) such that u- ∈ V ′- 1 and u- ̸∈ V - 1 . From these two inputs, we know the relations between i-, i+, j- and j+ (since j- &lt; j+ must hold). Since we know these relations, and since the sequence exists, f must have accepted that c(u, u′ ) is holds. This is true for all c ∈ C, so (Y1 : Yn) must be a solution for I. To verify that this solution also fulfills the overlap requirement, we at each step have v which is handled such that no value in V ever drops below 0. Hence we have a 'yes'-instance if R(∅, (), (), V -) &gt; 0.

For completeness, take an ordered partition Y = (Y1 : Yi) over V - ∪ V + satisfying our arbitrary instance I. Given this ordered partition, iterative construct a sequence of R(V - 1 ,X, v, V - 2 ) and and choose x- and y such that x+ = Yj ∩ V + and y = Yj ∩ V -, starting from R(∅, (), (), V -) and Y1, working towards Yi and R(V -, (), (), ∅). Now, observe that for X = (X1 : Xi′) we have that X1 ⊆ Yl, . . . , Xj ⊆ Yl+i′-1, and V - 2 = V - ∩ ⋃iu=l+i′ Yu, which means that when placing Yl, we will know the relations between all intervals ending in Yl, and all intervals ending later. Since these relations are the same as those in Y , f will always return a value greater than 0. Similarly, v will never contain a value less than 0, since the numbers in v simply counts how many overlaps have occurred for corresponding intervals. The ordering (Y1 : Yn) will also be tested as every sub-ordering of size at most k will be found by brute-force enumeration. So, if given a 'yes'- instance, we will reach R(V -, (), (), ∅) = 1 and so we have R(V - 1 ,X, v, V - 2 ) &gt; 0 for every other R in our sequence (including R(∅, (), (), V -)). Hence, this approach is correct. The complexity analysis is straightforward and the proof is omitted due to space constraints.

Let us also remark that this algorithm, as well as the one in Section 4.2, solve the more general problem of counting the number of solutions (i.e., the number of satisfying partial orders or ordered partitions)

## 5 Concluding Remarks

We explored how a multivariate complexity analysis can generate interesting cases with significant complexity improvements compared to the classical case of single parameters. This led to the introduction of the classes FPE and XE which turned out to be the natural exponential-time analogoues of the well-known classes FPT and XP. We proved several fundamental properties of these classes and gave examples of XE and FPE from qualitative reasoning. These algorithms are significantly faster than existing methods (provided the coarse-grained parameters stay relatively small) and constitute an important breakthrough for single-exponential time algorithms in qualitative reasoning.

Systematically classifyingXE andFPE. The overarching open question is to classify problems and parameters in terms of XE or FPE membership (or neither, under assumptions such as the ETH). Here, qualitative spatial reasoning problems (such as the REGION CONNECTION CALCULUS) seem to be a promising continuation since the NP-hard cases in general are not known to be solvable in single-exponential time. More generally, is it possible to find canonical parameters which result in FPE algorithms, similarly to how parameters such as tree-width almost always results in FPT algorithms? Identifying such parameters could open up entirely new algorithmic approaches for qualitative reasoning, in particular, and infinite-domain CSPs, in general.

Limited versus unlimited equality. The algorithm in Section 4.3 for k-CSP(A) has similarities to the one in [McDiarmid, 2003] for the CHANNEL ASSIGNMENT PROBLEM with bounded edge-length, making the two problems interesting to compare. One interpretation is that k-CSP(A) belongs to FPE because the problem bounds the number of intervals that may be equal (since they overlap), which is not true for CHANNEL ASSIGNMENT, which seemingly prevents our approach from proving FPE membership. However, if one limits the size of equivalence classes in the same sense in the CHANNEL ASSIGNMENT PROBLEM, this new problem would naturally fall into FPE, using just a slight modification of the original algorithm. Is this a problem specific behaviour, or is it a deeper difference between FPE and XE?

Extending and improving the algorithms. The algorithm in Section 4.2 and Section 4.3 can likely be improved to handle higher-arity constraints, although it would make the presentation and the analysis significantly more complex. Another interesting direction is to consider different parameters: the algorithm from Section 4.2 can very likely be modify to use the width of the partial order as the coarse-grained parameter instead of effective width, but it is less clear whether the dimension of a partial order is sufficient for an XE-algorithm.

## Acknowledgements

We thank 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.

## References

1. [Allen and Koomen, 1983] James F. Allen and Johannes A. G. M. Koomen. Planning using a temporal world model. In Alan Bundy, editor, Proceedings of the 8th International Joint Conference on Artificial Intelligence (IJCAI-1983), pages 741-747, 1983.
2. [Allen, 1983] James F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26:510- 521, 01 1983.
3. [Anger et al., 1999] Frank D. Anger, Debasis Mitra, and Rita V. Rodríguez. Satisfiability in nonlinear time: Al- gorithms and complexity. In Proceedings of the 12th In- ternational Florida Artificial Intelligence Research Society Conference (FLAIRS-1999), pages 406-411, 1999.
4. [Anger, 1989] Frank D. Anger. On Lamport's interprocessor communication model. ACM Transactions on Program- ming Languages and Systems, 11(3):404-417, 1989.
5. [Björklund et al., 2009] Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion- exclusion. SIAM Journal on Computing, 39(2):546-563, 2009.
6. [Bodirsky and Dalmau, 2013] Manuel Bodirsky and Víctor Dalmau. Datalog and constraint satisfaction with infi- nite templates. Journal of Computer and System Sciences, 79(1):79-100, 2013.
7. [Bringmann and Künnemann, 2018] Karl Bringmann and Marvin Künnemann. Multivariate fine-grained complexity of longest common subsequence. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2018), pages 1216-1235, 2018.
8. [Chu et al., 2021] Huairui Chu, Mingyu Xiao, and Zhe Zhang. An improved upper bound for SAT. Theoretical Computer Science, 887:51-62, 2021.
9. [Dabrowski et al., 2021] Konrad K. Dabrowski, Peter Jons- son, Sebastian Ordyniak, and George Osipov. Solving infinite-domain CSPs using the patchwork property. In Proceedings of the 35th AAAI Conference on Artificial In- telligence (AAAI-2021), pages 3715-3723, 2021.
10. [Denis and Muller, 2011] Pascal Denis and Philippe Muller. Predicting globally-coherent temporal structures from texts via endpoint inference and graph decomposition. In Pro- ceedings of the 22nd International Joint Conference on Ar- tificial Intelligence (IJCAI-2011), pages 1788-1793, 2011.
11. [Dorn, 1995] Jürgen Dorn. Dependable reactive event- oriented planning. Data & Knowledge Engineering, 16(1):27-49, 1995.
12. [Dylla et al., 2017] Frank Dylla, Jae H. Lee, Till Mossakowski, Thomas Schneider, André Van Delden, Jesper Van De Ven, and Diedrich Wolter. A survey of qualitative spatial and temporal calculi: Algebraic and computational properties. ACM Computing Surveys, 50(1):7:1-7:39, 2017.
13. [Eriksson and Lagerkvist, 2021] Leif Eriksson and Victor Lagerkvist. Improved algorithms for Allen's interval alge- bra: a dynamic programming approach. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI-2021), pages 1873-1879, 2021.
14. [Fomin et al., 2007] Fedor V. Fomin, Pinar Heggernes, and Dieter Kratsch. Exact algorithms for graph homomor- phisms. Theory of Computing Systems, 41(2):381-393, 2007.
15. [Golumbic and Shamir, 1993] Martin C. Golumbic and Ron Shamir. Complexity and algorithms for reasoning about time: A graph-theoretic approach. Journal of the ACM, 40(5):1108-1133, 1993.
16. [Jonsson and Lagerkvist, 2017] Peter Jonsson and Victor Lagerkvist. An initial study of time complexity in infinite- domain constraint satisfaction. Artificial Intelligence, 245:115-133, 2017.
17. [Jonsson and Lagerkvist, 2018] Peter Jonsson and Victor Lagerkvist. Why are CSPs based on partition schemes com- putationally hard? In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Sci- ence (MFCS-2018), volume 117, pages 43:1-43:15, 2018.
18. [Jonsson and Lagerkvist, 2020] Peter Jonsson and Victor Lagerkvist. Lower bounds and faster algorithms for equality constraints. In Proceedings of the Twenty-Ninth Interna- tional Joint Conference on Artificial Intelligence (IJCAI- 2020), pages 1784-1790, 2020.
19. [Jonsson et al., 2021] Peter Jonsson, Victor Lagerkvist, and George Osipov. Acyclic orders, partition schemes and CSPs: Unified hardness proofs and improved algorithms. Artificial Intelligence, 296:103505, 2021.
20. [Lamport, 1986] Leslie Lamport. The mutual exclusion prob- lem: Part I-a theory of interprocess communication. Jour- nal of the ACM, 33(2):313-326, 1986.
21. [McDiarmid, 2003] Colin McDiarmid. On the span in chan- nel assignment problems: bounds, computing and counting. Discrete Mathematics, 266(1):387 -397, 2003.
22. [Mudrová and Hawes, 2015] Lenka Mudrová and Nick Hawes. Task scheduling for mobile robots using interval algebra. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA-2015), pages 383-388, 2015.
23. [Song and Cohen, 1988] Fei Song and Robin Cohen. The in- terpretation of temporal relations in narrative. In Howard E. Shrobe, Tom M. Mitchell, and Reid G. Smith, editors, Pro- ceedings of the 7th National Conference on Artificial Intel- ligence (AAAI-1988),, pages 745-750, 1988.
24. [Wahlström, 2011] Magnus Wahlström. New plain- exponential time classes for graph homomorphism. Theory of Computing Systems, 49(2):273-282, 2011.