Paper deep dive
Maximum Satisfiability of Simple Temporal Problems
Johannes K. Fichte, Johanna Groven, Peter Jonsson, Victor Lagerkvist, Jorke M. de Vlas
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:The Simple Temporal Problem (STP) is a core framework for quantitative temporal constraints. As STP data can be inconsistent, we study MAXSTP: compute a maximum-cardinality consistent subset of constraints. This extension is NP-hard, and we analyze its parameterized complexity under measures that capture practically relevant instance features: the number of variables $n$ (instance scale), the maximum coefficient magnitude $k$ (numeric range), and structural parameters of the constraint graph such as treewidth $tw$ (decomposability) and vertex cover size $vc$ (density). We show that MAXSTP is W[1]-hard parameterized by $n$, implying that $n$ and parameters that depend on $n$ (including $tw$ and $vc$) are insufficient for fixed-parameter tractability. For combined parameters, we give an $O^*(k^n)$-time algorithm, yielding single-exponential solvability for fixed $k$. While $k+tw$ remains W[1]-hard, MAXSTP is in XP via an $O^*((n\cdot k)^{tw})$ algorithm. Our results suggest that MAXSTP is often computationally harder than optimizing qualitative CSPs. We verify that many such problems (including RCC-8 and Allen's algebra) are FPT when parameterized by $n$ or $tw$. However, we also demonstrate that FPT algorithms for MAXSTP are indeed possible but with other parameters such as $k + vc$.
Tags
Links
- Source: https://arxiv.org/abs/2607.23785v1
- Canonical: https://arxiv.org/abs/2607.23785v1
Trouble viewing inline? Open PDF directly →
Full Text
55,133 characters extracted from source content.
Expand or collapse full text
Maximum Satisfiability of Simple Temporal Problems Johannes K. Fichte Johanna Groven Peter Jonsson Victor Lagerkvist Jorke M. de Vlas Abstract The Simple Temporal Problem (STP) is a core framework for quantitative temporal constraints. As STP data can be inconsistent, we study MaxSTP: compute a maximum-cardinality consistent subset of constraints. This extension is NP-hard, and we analyze its parameterized complexity under measures that capture practically relevant instance features: the number of variables n (instance scale), the maximum coefficient magnitude k (numeric range), and structural parameters of the constraint graph such as treewidth tw (decomposability) and vertex cover size vc (density). We show that MaxSTP is W[1]-hard parameterized by n, implying that n and parameters that depend on n (including tw and vc) are insufficient for fixed-parameter tractability. For combined parameters, we give an O∗(kn)O^*(k^n)-time algorithm, yielding single-exponential solvability for fixed k. While k+k+ tw remains W[1]-hard, MaxSTP is in XP via an O∗((n⋅k))O^*((n· k) tw) algorithm. Our results suggest that MaxSTP is often computationally harder than optimizing qualitative CSPs—we verify that many such problems (including RCC-8 and Allen’s algebra) are FPT when parameterized by n or tw. However, we also demonstrate that FPT algorithms for MaxSTP are indeed possible but with other parameters such as k+k+ vc. 1 Introduction The simple temporal problem [18] (STP) is a fundamental quantitative temporal constraint problem in AI. The task is to decide if a set of constraints (for a,b∈ℤ∪−∞,∞a,b ∪\-∞,∞\) of the form a≤x−y≤ba≤ x-y≤ b, or a≤x≤ba≤ x≤ b, is consistent, in the sense that it admits at least one satisfying assignment. One of the original motivations for introducing this formalism is that it is a simple and efficient way that makes it possible to detect inconsistencies in temporal data. The STP problem is the most well-known temporal framework with thousands of reported applications [29]. Early success stories include e.g. autonomous vehicles in space exploration [11, 27], and temporal planning [35, Chapter 14] while more recent examples include e.g. managing temporal data in robotic scheduling [41] and multi-agent systems [10]. STP can be decided in polynomial time but has limited expressive power for handling uncertainty. To cope with this several extensions have been considered, e.g., by allowing disjunctions [18, 40], and, more recently [15], by allowing a small set of inconsistencies. Thus, we want to identify a maximum consistent subset of the data: this is the maximum constraint satisfaction problem (MaxCSP). Such problems are well-studied in the AI literature (see, for instance, see [13, 14, 12, 6] and the references therein). Its Boolean analogue is the ubiquitous MaxSAT problem where clauses in Boolean CNF are considered [2]. An annual solver evaluation (MaxSAT Evaluation) collects applications, and instances, and tests solvers practically [4]. Hence, we study the problem MaxSTP: given an STP instance and m≥0m≥ 0, decide if it possible to obtain a satisfiable instance by keeping at least m constraints. We first observe that MaxSTP, in contrast to STP, is NP-hard [15] so we shift to a parameterized complexity view where we identify parameters that correlate to a “hidden structure” so that the problem can be solved efficiently. In the best case, we can solve a problem in f(k)⋅‖I‖O(1)f(k)·||I||^O(1) time, where I is an instance with parameter k∈ℕk , ‖I‖||I|| the number of bits required to represent it, and f:ℕ→ℕf a computable function. A problem admitting such an algorithm is said to be fixed parameter tractable (FPT). The parameterized complexity of MaxSAT is well-studied (cf. [20]) and recently also solvers that employ and improve on parameterized techniques (such as treewidth) have been introduced [3]. However, there is little reason to believe that these results carry over to the STP setting. In fact, we will establish that MaxSTP is fundamentally different. For MaxSTP we may immediately remark that the parameter m in itself hardly makes sense since we would expect it to grow with the instance size. Here, we diverge from Dabrowski et al. [15] who considered the dual problem AlmostCSP where the task is instead to delete at most m constraints — the problems are clearly classically equivalent but differ under parameterized and approximation complexity. Instead, we propose the magnitude (C) mag(C), the largest absolute value of any constant appearing in an instance (V,C)(V,C). Towards FPT algorithms we first (in Section 3) investigate the parameterized complexity of MaxSTP with parameter n=|V|n=|V|. Observe that this for many problems, e.g., finite-domain CSPs, and qualitative reasoning problems such as Allen’s interval algebra and the region connection calculus, is an incredibly strong parameter that gives trivial FPT algorithms by exhaustive enumeration. This is not possible for MaxSTP but we manage to construct an algorithm with a running time dominated by (C)n mag(C)^n, i.e., for fixed magnitude (C) mag(C) the problem is solvable in single-exponential time. We match this with a sharp W[1]-hardness proof (under parameter n) via a Sidon set construction from the multicolor clique problem. Under the conjecture that 3-SAT is not solvable in subexponential time (the exponential-time hypothesis (ETH) we can even infer that MaxSTP is not solvable in 2o(nlog(C)+f(n))2^o(n mag(C)+f(n)) time for any computable function f:ℕ→ℕf , i.e., we have matching upper and lower bounds for MaxSTP when analyzed with n. An important consequence of this lower bound is that it rules out FPT algorithms for e.g. graph parameters that depend on n, such as treewidth, showing the need to consider multiple parameters to reach FPT. We analyze this in Section 4 and consider magnitude combined with either treewidth (tw), or the size of a minimal vertex cover (vc). Here, we begin with the weaker parameter vc and construct a branching based FPT algorithm that exploits the parameters to bound the domain of each variable. Treewidth turns out to be less favourable and, building on the construction in Section 3, we give a W[1]-hardness proof. Treewidth still turns out to be useful, however, and while insufficient for FPT, it can still be used to obtain an XP algorithm. Put together, MaxSTP is fairly resilient, but not immune, to FPT algorithms, and parameters that normally work (e.g., n=|V|n=|V| or tw) lead to W[1]-hardness. In Section 5 we compare this to the corresponding question for qualitative reasoning, i.e., frameworks where we only care about the relations between variables, and not their precise numerical values. Allen’s interval algebra, the region connection calculus, and the cardinal direction calculus, are all well-known examples of NP-hard qualitative reasoning problems. They can be formulated as infinite-domain CSPs for “well-behaved” templates that often makes it possible to use parameters and techniques from the finite-domain case. Here, the gap between CSP and MaxCSP is much more narrow and DP-style algorithms for the former can often be extended to the latter. We exemplify a general criterion for when this is possible which, for example, captures Allen’s interval algebra CSP(Allen) CSP(Allen), where we get FPT for MaxCSP(Allen) MaxCSP(Allen) with parameter tw as well as an improved DP algorithm under parameter n. Hence, the MaxCSP problem seems to be fundamentally different for qualitative versus quantitative reasoning. 2 Preliminaries We begin by presenting the notation, the (maximum) CSPs, and the most relevant concepts from parameterized complexity. To express running times, we sometimes use the notation O∗(⋅)O^*(·) that hides factors polynomial in the input size. 2.1 Constraint Satisfaction A constraint language A is a set of relations over a set D (a domain). The constraint satisfaction problem over A (CSP() CSP( A)) is defined as follows: CSP(A) Input: A tuple (V,C)(V,C), where V is a set of variables and C is a multiset of constraints of the form R(v1,…,va)R(v_1,…,v_a), where a is the arity of R, v1,…,va∈Vv_1,…,v_a∈ V, and R∈R∈ A. Question: Is there a function f:V→Df:V→ D such that (f(v1),…,f(va))∈R(f(v_1),…,f(v_a))∈ R for every R(v1,…,va)∈CR(v_1,…,v_a)∈ C? The function f is said to be a a satisfying assignment or simply a solution. Having a multiset of constraints is a simple way of introducing a weighting mechanism for constraints in the forthcoming MaxCSP problem; sometimes more elaborate ways are considered but this one is sufficient for our needs. The value of an assignment φ for I=(V,C)I=(V,C) is the number of constraints in C satisfied by φ . The maximum constraint satisfaction problem (MaxCSP() MaxCSP( A)) is defined as follows: MaxCSP(A) Input: An instance (V,C)(V,C) of CSP() CSP( A) and an integer m. Question: Is there a set X⊆CX C such that |X|≥m X ≥ m and (V,X)(V,X) is satisfiable? Given an instance ((V,C),m)((V,C),m) of MaxCSP() MaxCSP( A), the set X can be computed with |C||C| calls to an algorithm for MaxCSP() MaxCSP( A). Hence, we can view MaxCSP() MaxCSP( A) as a decision problem without loss of generality. The primal graph of a CSP instance (V,C(V,C) has vertex set V and and two vertices are joined if their corresponding variables occur together in a constraint in C. We view the primal graph as a simple undirected graph, even though it is technically a graph with loops on every vertex (equivalently, one may only join distinct vertices). 2.2 Relations and Constraint Languages Dechter et al. [18] introduced the highly influential simple temporal problem. Let SbS_b be the set of binary relations Ba,b=(x1,x2)∈ℚ2∣a≤x1−x2≤bB_a,b=\(x_1,x_2) ^2 a≤ x_1-x_2≤ b\ for endpoints a∈ℤ∪−∞a ∪\-∞\ and b∈ℤ∪∞b ∪\∞\ such that a≤ba≤ b, (a,b)≠(−∞,∞)(a,b)≠(-∞,∞). Let SuS_u be the set of unary relations Ua,b=(x)∈ℚ∣a≤x≤bU_a,b=\(x) a≤ x≤ b\ for endpoints a∈ℤ∪−∞a ∪\-∞\ and b∈ℤ∪∞b ∪\∞\ such that a≤ba≤ b, (a,b)≠(−∞,∞)(a,b)≠(-∞,∞). CSP(S) CSP(S) where S=Sb∪SuS=S_b _u is known as the simple temporal problem (STP). To aid readability, we sometimes denote the constraint Ra,b(x,y)R_a,b(x,y) by a≤x−y≤ba≤ x-y≤ b. We follow e.g. [40] and assume that bounding values are integers. This implies that every satisfiable instance of STP admits an integer solution (see Dechter et al. [18, Section 3]). We can thus work over ℤZ without loss of generality. Given an STP relation Ra,bR_a,b, we let (Ra,b)=max(|a|,|b|∖∞) mag(R_a,b)= (\|a|,|b|\ \∞\). We say that (Ra,b) mag(R_a,b) is the magnitude of Ra,bR_a,b. Note that the magnitude of, for instance, R1,∞R_1,∞ is 1. If X is a set of relations or constraints, then the definition of (⋅) mag(·) extends naturally: (X)=maxR∈X(R) mag(X)= _R∈ X mag(R), i.e. (X) mag(X) is the least upper bound on absolute values of all numerical bounds appearing in the relations of X. Let MaxSTP denote the problem MaxCSP(S) MaxCSP(S) and MaxSTPb MaxSTP_b denote MaxSTP restricted to binary relations. We will look at restricted versions of MaxSTP so we let S(k)S^(k), k∈ℕk , denote S restricted to relations R satisfying (R)≤k mag(R)≤ k and let MaxSTP(k) MaxSTP^(k) denote MaxCSP(S(k)) MaxCSP(S^(k)) (and MaxSTPb(k) MaxSTP_b^(k) is defined in the obvious way). We finally note that the CSP(Sb)(S_b) problem is invariant under translation, i.e. if φ:V→ℤ :V satisfies an instance (V,C)(V,C), then so does φ′(v)=φ(v)+c (v)= (v)+c for all v∈Vv∈ V and an arbitrary c∈ℤc . Thus, we can pick any variable in V and assume that its value is zero without loss of generality. We call such a variable a zero variable. Augmenting an instance of STP with a zero variable z allows us to express unary constraints in SbS_b, e.g. the constraint 0≤x−z≤20≤ x-z≤ 2 is equivalent to x∈0,1,2x∈\0,1,2\. 2.3 Parameterized Complexity We use the framework of parameterized complexity [21, 25, 36], where the run-time of an algorithm is studied with respect to a parameter p∈ℕp and the input size n. A parameterized problem is then a subset of Σ∗×ℕ ^*×N (where Σ is the input alphabet). The idea is that the parameter describes the structure of the instance in a computationally meaningful way. Here, the most favourable complexity class is FPT, which contains all problems that are fixed-parameter tractable (FPT), i.e. can be decided in f(p)⋅nO(1)f(p)· n^O(1) time, where f is a computable function. The next best option is the complexity class XP, which contains all problems decidable in nf(p)n^f(p) time, i.e. the problems solvable in polynomial time when the parameter p is bounded. Clearly, FPT⊆XP FPT XP and this inclusion is strict (see e.g. [25, Cor. 2.26]). It is significantly better if a problem is in FPT than in XP since the order of the polynomial factor in the former case does not depend on the parameter p. Finally, the class pNP contains all problems that can be decided in f(p)⋅nO(1)f(p)· n^O(1) time by a non-deterministic algorithm for some computable function f. It is known that a problem is pNP-hard (under FPT-reductions; see below) if it is NP-hard for some constant value of the parameter. Problems that are pNP-hard are considered to be significantly harder than those in XP since a problem that is pNP-hard cannot be in XP unless P = NP. Reductions between parameterized problems must take the parameter into account. To this end, we use parameterized reductions (or FPT-reductions). Let L1L_1 and L2L_2 denote parameterized problems with L1⊆Σ1∗×ℕL_1 _1^*×N and L2⊆Σ2∗×ℕL_2 _2^*×N. A parameterized reduction from L1L_1 to L2L_2 is a mapping P:Σ1∗×ℕ→Σ2∗×ℕP: _1^*×N→ _2^*×N such that 1. (x,k)∈L1(x,k)∈ L_1 if and only if P((x,k))∈L2P((x,k))∈ L_2, 2. the mapping can be computed by an FPT-algorithm with respect to the parameter k, and 3. there is a computable function g:ℕ→ℕg:N→N such that for all (x,k)∈L1(x,k)∈ L_1 if (x′,k′)=P((x,k))(x ,k )=P((x,k)), then k′≤g(k)k ≤ g(k). The class W[1] W[1] contains all problems that are FPT-reducible to Independent Set parameterized by the size of the solution set. Showing W[1] W[1]-hardness (by an FPT-reduction) for a problem rules out the existence of an FPT algorithm under the assumption FPT≠W[1] FPT≠ W[1]. To obtain sharper bounds we sometimes use the exponential-time hypothesis (ETH), which is an ubiquitous computational hardness assumption, implying that satisfiability of 3-CNF Boolean formulas (3-SAT) with n variables cannot be solved in 2o(n)2^o(n) time. Tree Decompositions and Treewidth A central parameter is treewidth which intuitively describes how far a graph is from being a tree. While the name was introduced by [38], the idea appeared much earlier in nonserial dynamic programming [5] and have been intensively applied in AI (e.g. bucket elimination [19]). A tree decomposition =(T,χ)T=(T,χ) of a graph G=(V,E)G=(V,E) consists of a rooted tree T and a mapping χ that assigns each node t∈V(T)t∈ V(T) a set χ(t)⊆Vχ(t) V, called bag, such that E(G)⊆u,v|t∈V(T),u,v⊆χ(t)E(G) \\u,v\\,|\,t∈ V(T),\u,v\ χ(t)\; and (i) for every v∈Vv∈ V, the nodes, for which the bag contains v, form a non-empty sub-tree of T. We let width()=max|χ(t)|−1:t∈Twidth(T)= \ χ(t) -1:t∈ T\. The treewidth of a graph G, denoted by (G) tw(G), is the minimum width(T)width(T) over all tree decomposition of G. Given an instance I of CSP, we use the phrase primal treewidth for the treewidth of the primal graph of I. For arbitrary but fixed w≥1w≥ 1, we can decide in linear time whether a graph has treewidth at most w and, if so, to compute a tree decomposition of width w [9]. 3 Bounded Magnitude is Necessary Exhaustive enumeration of all subsets of constraints solves MaxSTP in O∗(2|C|)⊆O∗(2‖I‖)O^*(2^|C|) O^*(2^||I||) time where ‖I‖||I|| is the number of bits required to represent the instance I. Since ‖I‖||I|| can be much larger than the number of variables n this bound says virtually nothing. We begin this section by constructing an algorithm with running time dominated by (C)n mag(C)^n, i.e., 2nlog(C)2^n mag(C). Thus, MaxSTP is solvable in single-exponential time for any fixed magnitude. Theorem 1. MaxSTPb MaxSTP_b can be solved in O∗((k+3)n)O^*((k+3)^n) time, where n=|V|n=|V| and k=(C)k= mag(C). Proof. We use dynamic programming and construct all relative positions of variables with respect to some boundary value moving to the right on the natural line. Specifically, we keep track of a partition of the n vertices in k+3k+3 groups: one group A<A_< containing vertices more than k below the boundary value, k+1k+1 groups A0,…,AkA_0,…,A_k containing variables exactly 0,…,k0,…,k below the boundary value, and one group A>A_> containing vertices at or above the boundary value. Note that the vertices at the boundary value can be either in A0A_0 or in A>A_>. Overall, this results in (k+3)n(k+3)^n states. We call variables in A<,A0,…,AkA_<,A_0,…,A_k as decided and variables in A>A_> as undecided. The algorithm starts in the state where A<=A0=…=Ak=∅A_<=A_0=…=A_k= and A>=VA_>=V and recursively moves variables from A>A_> to A<A_<, maintaining that for each configuration (A<,A0,…,Ak,A>)(A_<,A_0,…,A_k,A_>), the maximum number of satisfied constraints between decided variables is saved. In each step, the two following transitions are considered: Transition 1. We pick any undecided variable v and assign it the current boundary value. This moves it from group A>A_> to group A0A_0. Since v is now decided, the subproblem needs to account for constraints involving v and other decided variables u. For all u∈Ai,0≤i≤ku∈ A_i,0≤ i≤ k, we have v−u=iv-u=i. For all u∈A<u∈ A_<, we have v−u>k=(C)v-u>k= mag(C). In both cases we know whether a constraint between v and u is satisfied. Transition 2. We increase the boundary by one. This merges A<A_< and AkA_k into a new group A<A_<, relabels each group AiA_i as Ai+1A_i+1 for i∈0,…,k−1i∈\0,…,k-1\, and adds a new empty group A0A_0. Since this transition does not change the decided variables or their relative differences, the solution to the corresponding subproblem is unchanged. We disable this transition when the groups A0,…,AkA_0,…,A_k are all empty as we can assume that without loss of generality, the gap between two variables will be at most k+1k+1 by k=(C)k= mag(C). Clearly, each path from the starting state to the final state (A<=VA_<=V) using these transitions corresponds to a potential solution to the MaxSTPb MaxSTP_b instance, and each potential solution corresponds to such a path. We now show in which order to visit all the states. Consider the quantity |A0|+2|A1|+…+(k+1)|Ak|+(k+2)|A<|. A_0 +2 A_1 +…+(k+1) A_k +(k+2) A_< . In the first transition, we add one variable to |A0| A_0 , hence this quantity increases by one. In the second transition, each variable from the groups A0,…,AkA_0,…,A_k moves to a group with a larger effect on this quantity, hence, outside of the edge case where all these groups are empty, it always increases. This shows that, when we visit the states ordered by this quantity, breaking ties arbitrarily, we can only visit a state after all states with a transition towards it have already been considered. Overall, this shows that the DP solves the MaxSTPb MaxSTP_b instance. Since there are (k+3)n(k+3)^n states, each state has at most n+1n+1 transitions, and each transition can be computed in linear time, the total runtime is O∗((k+3)n)O^*((k+3)^n). ∎ We complement this upper bound by a matching lower bound (under standard complexity theoretical assumptions) for the parameter n=|V|n=|V|. Here, it is important to recall that n is a very strong parameter that gives trivial FPT algorithms for all finite-domain CSPs and infinite-domain qualitative reasoning problems. As such, it is a very useful lower bound since it can also (as we will show in Theorem 4) be used to obtain lower bounds for all reasonable graph parameters. The heart of our reduction is the Multicolor Clique problem. Multicolor Clique Input: A graph G=(V,E)G=(V,E) with a vertex coloring fC:V→Cf_C V→ C to some color set C such that each edge is between vertices of different colors. Param.: The number of colors |C| C Question: Is there a clique in G with exactly one vertex from each color? Theorem 2 (Theorem 5.2 in [33]). Multicolor Clique is (1) W[1]-hard and (2) cannot be solved in f(c)no(c)f(c)n^o(c) time unless the ETH fails, where c=|C|c= C is the number of colors, n=|V|n= V the number of vertices, and f:ℕ→ℕf:N any computable function. Our reduction is based on Sidon sets: a set S of integers such that the sum of any pair of its elements is unique, i.e. if a+b=c+da+b=c+d for a,b,c,d∈Sa,b,c,d∈ S, then a,b=c,d\a,b\=\c,d\. Differences are easier to use in our proofs so we use an equivalent condition: for all a,b,c,d∈Sa,b,c,d∈ S such that a≠ba≠ b and c≠dc≠ d, a−b=c−da-b=c-d holds if and only if a=ca=c and b=db=d. The order of a Sidon set is the number of elements in it and the length is the difference between its maximal and minimal elements. For example, 0,1,4,6\0,1,4,6\ is a Sidon set (see Figure 1) of order 44 with length 66. It is well-known that ”reasonable” Sidon sets are computable in polynomial time. For instance, Dabrowski et al. [17, Section 2.3] describe how a Sidon set of order k and length 8k28k^2 can be computed in polynomial time. b=0b=0 b=1b=1 b=4b=4 b=6b=6 a=0a=0 0 -1 -4 -6 a=1a=1 1 0 -3 -5 a=4a=4 4 3 0 -2 a=6a=6 6 5 2 0 Table 1: The set S=0,1,4,6S=\0,1,4,6\ is a Sidon set: a−ba-b has distinct values whenever a≠ba≠ b and a,b∈Sa,b∈ S. Theorem 3. MaxSTPb MaxSTP_b (and thus MaxSTP) is W[1]-hard when parameterized by the number of variables. It cannot be solved in 2o(nlogk+f(n))2^o(n k+f(n)) time unless the ETH fails where n=|V|n= V is the number of variables, k=(C)k= mag(C) the magnitude, and f:ℕ→ℕf any computable function. Proof. We present a reduction from Multicolor Clique to an instance of MaxSTPb MaxSTP_b. Let (G=(V,E),fC)(G=(V,E),f_C) be an instance of Multicolor Clique with n vertices, m edges and c=|C|c=|C| colors. We begin by introducing variables x1,…,xcx_1,…,x_c for each color and a zero variable z. We construct a Sidon set S=s1,…,snS=\s_1,…,s_n\ and add the constraints xfC(1)−z=s1,xfC(2)−z=s2,…xfC(n)−z=sn,x_f_C(1)-z=s_1,x_f_C(2)-z=s_2,… x_f_C(n)-z=s_n, which we make costly to delete by repeating them m+1m+1 times. Additionally, for each edge (u,v)∈E(u,v)∈ E, we add the constraint xfC(u)−xfC(v)=su−svx_f_C(u)-x_f_C(v)=s_u-s_v. This completes our reduction. Note that we now have (m+1)n+m(m+1)n+m constraints. Let W:=z,x1,…,xcW:=\z,x_1,…,x_c\ the resulting set of variables and D the resulting set of constraints. Clearly, (W,D)(W,D) can be computed in polynomial time. We now verify that G contains a multicolored clique if and only if ((W,D),N)((W,D),N) is a yes-instance of MaxSTPb MaxSTP_b where N:=c(m+1)+(c2)N:=c(m+1)+ c2. Forward direction. Assume G contains a multicolored clique K. Let g:C→Kg C→ K denote for each color the vertex from K that has this color. Define h:W→ℤh W such that h(z)=0h(z)=0 and h(xi)=sg(i)h(x_i)=s_g(i). We show that h is a solution to the MaxSTPb MaxSTP_b instance. Each edge (u,v)∈K(u,v)∈ K corresponds to the constraint xfC(u)−xfC(v)=su−svx_f_C(u)-x_f_C(v)=s_u-s_v. Since h(xfC(u))−h(xfC(v))=sg(fC(u))−sg(fC(v))=su−svh(x_f_C(u))-h(x_f_C(v))=s_g(f_C(u))-s_g(f_C(v))=s_u-s_v, these (c2) c2 constraints are satisfied. For each vertex v∈Kv∈ K, consider the constraint xfC(v)−z=svx_f_C(v)-z=s_v, which was repeated m+1m+1 times. Since h(xfC(v))−h(z)=sg(fC(v))−0=svh(x_f_C(v))-h(z)=s_g(f_C(v))-0=s_v, we also satisfy this, resulting in an additional c(m+1)c(m+1) satisfied constraints. In total, we satisfy at least N constraints. Backward direction. Assume ((W,D),N)((W,D),N) is a yes-instance and let h:W→ℤh W be a solution. By globally adding a suitable constant, we assume that h(z)=0h(z)=0. For each variable xix_i, all constraints between xix_i and z are disjoint up to the m+1m+1 time repetition, hence we satisfy either 0 or m+1m+1 such constraints. Since there are only m constraints not of this form, we must satisfy m+1m+1 such constraints for each variable; if not, we satisfy at most (c−1)(m+1)+m<c(m+1)<N(c-1)(m+1)+m<c(m+1)<N constraints. It follows that xix_i is assigned a value sus_u for some u∈Vu∈ V with fC(u)=if_C(u)=i. Let g:C→Vg C→ V be the function mapping each i to the corresponding u. Now consider two variables xix_i and xjx_j. As S is a Sidon set, and both xix_i and xjx_j are assigned values from S, every constraint of the form xfC(u)−xfC(v)=su−svx_f_C(u)-x_f_C(v)=s_u-s_v with fC(u)=if_C(u)=i and fC(v)=jf_C(v)=j is only satisfied if xix_i is assigned sus_u and xjx_j is assigned svs_v. It follows that we can only satisfy at most one such constraint between xix_i and xjx_j. In order to satisfy c(m+1)+(c2)c(m+1)+ c2 constraints in total, we must satisfy exactly one such constraint for each pair (xi,xj)(x_i,x_j) as there are no other remaining constraints. This shows that, for each xix_i and xjx_j, the constraint xi−xj=sg(i)−sg(j)x_i-x_j=s_g(i)-s_g(j) must exist. That is, g(i)g(i) and g(j)g(j) are connected in the original graph. Hence, the image of g is a multicolored clique. Since the total number of variables in W is n′:=c+1n :=c+1, the reduction is FPT. This shows W[1]-hardness. Since the absolute values of the integers appearing in the constraints do not exceed k′:=sn<8n2k :=s_n<8n^2, any algorithm solving MaxSTP in 2o(n′logk′+f′(n′))2^o(n k +f (n )) time for some f′f can be used to solve Multicolor Clique in 2o((c+1)log(8n2)+f′(c+1))=2f′(c+1)⋅no(c)2^o((c+1) (8n^2)+f (c+1))=2^f (c+1)· n^o(c) time. This contradicts the ETH by Theorem 2. ∎ This lower bound has significant consequences for virtually all other parameters. Theorem 4. If κ is a computable graph parameter, then MaxSTP is W[1]-hard when parameterized by κ of primal graph. Proof. As κ is computable, the function f:ℕ→ℕf where f(k)f(k) is the κ of a clique on k vertices is computable. Let G=(V,E)G=(V,E) be an instance of the Multicolor Clique problem with n′n variables and k′k colors. We use the same reduction as in the proof of Theorem 3. The primal graph of (W,D)(W,D) is now a clique on n=k′+1n=k +1 vertices hence κ of primal graph is f(k′+1)f(k +1), so the reduction is FPT. As Multicolor Clique is W[1]-hard, this gives W[1]-hardness for MaxSTP. ∎ 4 Parameterized Complexity Results Section 3 shows that any reasonable parameterization needs to take the magnitude into account. Thus, we now consider the parameterized complexity with parameter magnitude. A straightforward reduction shows the following pNP-hardness result. Theorem 5. MaxSTPb MaxSTP_b is pNP-hard when parameterized by mag. Proof. We use the following NP-hard problem [30]. Maximum Acyclic Subgraph (MAS) Input: A directed graph D=(V,A)D=(V,A) and an integer m. Question: Is there a set X⊆AX A such that |X|≥m|X|≥ m and (V,X)(V,X) is acyclic? Let ((V,A),m)((V,A),m) be an arbitrary instance of MAS. Construct an instance ((V,C),m)((V,C),m) of MaxSTPb MaxSTP_b where each arc vw∈Avw∈ A is replaced by the constraint v−w≤−1v-w≤-1. This constraint can be viewed as enforcing that f(v)<f(w)f(v)<f(w) for any solution f. It is clear that ((V,A),m)((V,A),m) is a yes-instance if and only if ((V,C),m)((V,C),m) is a yes-instance. Furthermore, (C)≤1 mag(C)≤ 1 so MaxSTPb MaxSTP_b is indeed pNP-hard when parameterized by magnitude. ∎ Hence, the magnitude does not help in itself, but it can be combined with other parameters. We explore this in Section 4.1 where we obtain a positive FPT result based on vertex cover, and in Section 4.2 where we consider treewidth. The latter parameterization turns out to be W[1]-hard but can be used for an XP algorithm. 4.1 Vertex Cover A vertex cover of a (directed or undirected) graph is a set of vertices that includes at least one endpoint of every edge. Given an instance I=(V,C)I=(V,C) of CSP, we let (I) vc(I) denote the size of the smallest vertex cover of the primal graph of I. We exhibit a connection between the structure of STP instances and the size of solution domains. Consider the directed edge-weighted distance graph ΔI=(V,A,w) _I=(V,A,w). This graph is constructed by for each constraint a≤x−y≤ba≤ x-y≤ b in C, adding arcs (x,y)(x,y), (y,x)(y,x) to A with weights w(x,y)=bw(x,y)=b, w(y,x)=−aw(y,x)=-a. Arcs of infinite weight are not added to A. Dechter et al. [18, Theorem 3.1]) have noted the following: an instance I of CSP() CSP( S) is satisfiable if and only if ΔI _I contains no directed cycle of total negative weight. Lemma 6. Let I=(V,C)I=(V,C) be an instance of b S_b where k=(C)k= mag(C) is its magnitude and d is the length of the longest simple path in the distance graph ΔI _I. If I has a solution, it has one where each value comes from the set 0,1,2,…,dk \0,1,2,…,dk \. Proof. Consider the distance graph ΔI _I. Since I has at least one solution, ΔI _I has no directed cycles of negative weight. Modify ΔI _I by adding a zero vertex z together with an arc of weight zero from each other vertex to z and let f:V→ℤf V be the function where, for each x∈Vx∈ V, f(x)f(x) is the length of the shortest path from x to z, measured by arc weight. This shortest distance exists since ΔI _I has no directed cycles of negative weight. Note that f is always non-positive since each shortest path is not longer than the path obtained by directly following the arc towards z. We now show that −f-f is a solution satisfying the lemma. First, −f-f is a solution to the instance: if some constraint x−y≤cx-y≤ c is not satisfied, then the path from x to z could be made shorter by going via y. Furthermore, −f-f is at least zero since f is non-positive. Finally, −f-f is at most dkdk since each shortest path consists of at most d arcs and each arc decreases the total length by at most k. This completes the proof. ∎ A consequence of Lemma 6 (which we will use in Section 4.2) is that solvable STP instances (V,C)(V,C) have a solution that only uses values from the set 0,1,2,…,(n−1)k \0,1,2,…,(n-1)k \ where n=|V|n=|V| and k=(C)k= mag(C). Theorem 7. MaxSTPb MaxSTP_b can be solved in O∗((2⋅k)n)O^*((2 vc· k) vcn), where n is the number of vertices and k the magnitude. In particular, it is FPT when parameterized by + mag+ vc. Proof. A graph with vertex cover vc has a longest simple path of length at most 2+12 vc+1: if there exists a longer path, then this path must contain two adjacent vertices that are not part of the vertex cover, and thus it does not cover all edges. Since the primal graph and the distance graph have the same vertex cover, Lemma 6 implies that a solvable instance has a solution with values from A=0,…,(2+1)kA=\0,…,(2 vc+1)k\. We now describe our algorithm. Let W with |W|= W = vc be a vertex cover. For each variable in W, guess a value from A. This results in |A| A vc branches. In each branch, we count how many constraints between vertices from W are satisfied. We then determine for every other variable v the largest number of constraints between v and W that can be satisfied by trying all |A| A options for v. Since there are no edges between vertices outside of W, these choices are all independent, hence we find the optimal value in this branch. By computing the maximum number of satisfied constraints over all branches, we find a solution to the instance. The overall runtime is O(|A|+1n)=O(((2+1)k)+1n)=O∗((2k)n).O ( A vc+1n )=O (((2 vc+1)k) vc+1n )=O^* ((2 vck) vcn ). ∎ 4.2 Treewidth We show that MaxSTPb(k) MaxSTP_b^(k) is W[1]-hard when parameterized by treewidth of primal graph for every k≥1k≥ 1 (MaxSTPb(0) MaxSTP_b^(0) is trivial since every constraint can be satisfied by assigning zero to all variables). Nevertheless, treewidth can be used to solve MaxSTP faster, and we construct an XP algorithm running in roughly (nk)(nk) tw time where k=(C)k= mag(C) and n=|V|n=|V|. 4.2.1 W[1]-hardness Our W[1]-hardness result is based on the proof of Theorem 3. Theorem 8. MaxSTPb(1) MaxSTP_b^(1) is W[1]-hard when parameterized by tw. Proof. Recall the reduction from Theorem 3. It results in a W[1]-hard instance of MaxSTPb MaxSTP_b whose primal graph is a clique on c+1c+1 vertices and each edge corresponds to an equality constraint of magnitude at most 8n28n^2, where c is the parameter and n is bounded by instance size. There can be multiple edges between the same vertices, but there are O(mn)O(mn) edges in total, where m is again bounded by instance size. We transform this instance into one with magnitude 1 by subdividing edges. Consider an edge (x,y)(x,y) corresponding to a constraint f(x)−f(y)=af(x)-f(y)=a with |a|≥2 a ≥ 2. Assume without loss of generality that a is positive. We replace this edge with a path of a edges on vertices x0,x1,…,xax_0,x_1,…,x_a where x0=x_0=x, xa=yx_a=y, and x1,…,xa−1x_1,…,x_a-1 are fresh variables. Each edge (xi−1,xi)(x_i-1,x_i) is given the constraint f(xi−1)−f(xi)=1f(x_i-1)-f(x_i)=1. The result is a graph on O(mn⋅n2)O(mn· n^2) vertices with magnitude 1. This new instance is equivalent to the original instance: an optimal solution to the new instance will break at most one edge in each path, and breaking one edge in a path is equivalent to breaking the original high-magnitude edge. Finally, we show that the resulting graph has bounded treewidth by giving a tree decomposition of size max(2,c) (2,c), which implies that the reduction is FPT and hence that MaxSTPb(1) MaxSTP_b^(1) is W[1]-hard when parameterized by tw. We begin with one bag B containing all c+1c+1 vertices from the original clique. For each path x0,x1,…,xax_0,x_1,…,x_a, we add a path of bags B1,…,BaB_1,…,B_a with Bi:=xi−1,xi,yB_i:=\x_i-1,x_i,y\ for 1≤i≤a1≤ i≤ a and where B1B_1 is adjacent to B. This results in a valid tree decomposition. The size of the largest bag is max(3,c+1) (3,c+1), hence the width is max(2,c) (2,c), which completes the proof. ∎ 4.2.2 XPAlgorithm We continue with our XP algorithm. Theorem 9. MaxSTPb MaxSTP_b can be solved in O∗((nk))O^*((nk) tw), where n is the number of vertices, k the magnitude, and tw the treewidth of the distance graph ΔI _I. Proof. We begin with a definition. Let T be a tree decomposition. We say that T is nice if it is rooted using some root r with χ(r)=∅χ(r)= , and each node t has one of the following types: • leaf node: χ(t)=∅χ(t)= and t has no children. • introduce node: t has one child t′t , and there exists a vertex v∈χ(t)v∈χ(t) such that χ(t′)=χ(t)∖vχ(t )=χ(t) \v\. • forget node: t has one child t′t , and there exists a vertex v∈χ(t′)v∈χ(t ) such that χ(t)=χ(t′)∖vχ(t)=χ(t ) \v\. • join node: t has two children t1,t2t_1,t_2 and χ(t)=χ(t1)=biχ(t2)χ(t)=χ(t_1)=biχ(t_2). Any tree decomposition can be modified into a nice tree decomposition of the same width in linear time. For a node t∈Tt∈ T, we define TtT_t as the subtree rooted at t, and define χ(Tt)=⋃t′∈Ttχ(t′)χ(T_t)= _t ∈ T_tχ(t ) as the set of all variables occurring in this subtree [8]. We use standard dynamic programming over a tree decomposition [39]. Let T be a nice tree decomposition of the primal graph ΔI _I with width tw. By a defining property of tree decompositions, for each constraint C, there exists at least one node whose bag contains all variables occurring in C. However, there may be several such nodes. To avoid double counting, we assign C to one such node, chosen arbitrarily. For each node t, we let CtC_t denote the constraints associated with t. By Lemma 6, noting that any simple path has length at most n−1n-1, we only need to look for solutions from the set S=0,1,2,…,(n−1)kS= \0,1,2,…,(n-1)k \. We now wish to compute the following information: for each node t, and each possible assignment f:χ(t)→Sf χ(t)→ S, what is the largest number of constraints that can be satisfied in any extension of f into an assignment f′:χ(Tt)→Sf χ(T_t)→ S where we only consider constraints that are associated with nodes from TtT_t? Let DP(t,f)DP(t,f) denote this value. Given t and f, we note that DP(t,f)DP(t,f) equals the number of constraints in CtC_t satisfied by f plus the following depending on the type of t. • leaf node: TtT_t contains no other constraints, hence we add nothing. • introduce node: let t′t be the child node. Any extension of f must extend the restriction f|χ(t′) .f |_χ(t ), hence we add the value DP(t′,f|χ(t′))DP(t , .f |_χ(t )). • forget node: let t′t be the child node and v the forgotten variable. For each i∈Si∈ S, let fif_i be the extensions of f into an assignment of χ(t′)χ(t ) where fi(v)=if_i(v)=i. Since any extension of f in χ(Tt)χ(T_t) extends some fif_i, we add the maximum maxi∈S(DP(t′,fi)) _i∈ S(DP(t ,f_i)). • join node: let t1t_1 and t2t_2 be the two child nodes. Since any extension of f to χ(Tt)χ(T_t) can be split into two independent extensions f1f_1 in χ(Tt1)χ(T_t_1) and f2f_2 in χ(Tt2)χ(T_t_2), we add the sum DP(t1,f)+DP(t2,f)DP(t_1,f)+DP(t_2,f). Finally, since the root r is empty, DP(r,∅)DP(r, ) holds the answer to the entire instance. For all nodes t except forget nodes, there are at most |S|+1 S tw+1 states and each state can be computed in O(|Ct|)O( C_t ) time. For forget nodes t, each state requires O(|S|+|Ct|)O( S + C_t ) time, but we have |χ(t)|<+1 χ(t) < tw+1 since the child node is larger and has size at most +1 tw+1, hence computing all states also requires O(|S|+1|Ct|)O( S tw+1 C_t ) time. Since there are O(n)O(n) nodes total, and all CtC_t sum to m, the total runtime is O(|S|+1(n+m))=O((nk))O( S tw+1(n+m))=O((nk) tw). ∎ 5 A Comparison with Qualitative Reasoning Qualitative reasoning is an influential subarea of AI where quantitative (e.g., numerical) relations are avoided in favour of qualitative relations. Well-known qualitative formalisms include Allen’s Interval algebra [1], the spatial RCC formalisms [37], and various cardinal direction calculi [26, 28, 32]. The intersection between qualitative reasoning and CSPs has been intensively studied, generating a large number of formalisms and results [7, 22]. Clearly, STP is is not qualitative since it is profoundly based in relations between numerical values. It is thus interesting to make comparisons between the MaxCSP for qualitative formalisms and MaxSTP. One approach [23, 24] for solving spatio-temporal CSPs is to construct the respective spatio-temporal orders using branching and merging two nodes in the branching tree if for all expansions of the respective partial orders corresponding to the nodes to total orders, either both total orders correspond to satisfying assignments or neither. We find that dynamic programming (DP) approaches exploiting this idea are often generalizable to MaxCSP. Furthermore, Dabrowski et al. [16] have proven that CSP() CSP( A) for constraint languages with the patchwork property (see [34]) are FPT parameterized by the treewidth of the primal graph. Patchwork states that the union of two satisfiable CSP instances whose constraints agree on their common variables is satisfiable. This result generalizes to MaxCSP, and shows, for instance, that MaxCSP(Allen) and MaxCSP(RCC8) are in FPT when parameterized by tw. We conclude the following. Observation. Let A be a finite constraint language with jointly-exhaustive and pairwise-disjoint relations such that CSP()( A) is decidable. (1). If CSP() CSP( A) is decidable in a time f(n)f(n) for some f(n)∈Ω∗(exp(n))f(n)∈ ^*( (n)) using DP and a search tree such that • any two nodes in the tree that are equivalent to each other (v∼wv w are merged in the branching procedure) are also equivalent to each other with respect to the number of satisfied constraints, i.e. appending the same path to both nodes will result in the same number of constraints being satisfied by the solutions of the respective leaves, • the number of constraints satisfied by each node is computable in polynomial time from parent nodes, • for each assignment of variables, there is a corresponding node in the search tree (in particular also unsatisfying assignments), then MaxCSP() MaxCSP( A) is solvable in time O∗(f(n))O^*(f(n)). (2). If A has the patchwork property and B is a finite structure whose relations are Boolean combinations of relations in A (i.e. relations definable by quantifier-free formulas that only contain the relations in A), then the problem MaxCSP() MaxCSP( B) is FPT parameterized by the treewidth of the primal graph. Consider Algorithm 2 from [24] that solves CSP(Allen) in time O∗((cn/logn)n)O^*((cn/ n)^n) by generating all possible records of a given instance. By altering the definition of a record slightly by including the constraints satisfied by the record in the record and altering the algorithm analogously to compute all possible records regardless of whether they contradict constraints, we construct an algorithm that computes MaxCSP(Allen) in time O∗((cn/logn)n)O^*((cn/ n)^n). Note, however, that in some instances we might need to reprove parts of the analysis that do not directly extend to MaxCSP. Consider e.g. Theorem 19 in [31] showing a O∗((cn/logn)n)O^*((cn/ n)^n) result for CSP(RCC-8). While the algorithm employs dynamic programming and is generalizable to MaxCSP, it reduces the problem to a tractable fragment of CSP(RCC-8) which is not proven to be tractable for MaxCSP. To extend this result, we would thus need to prove that the reduced fragment is also tractable for MaxCSP or at least solvable in O∗((cn/logn)n)O^*((cn/ n)^n). 6 Concluding Remarks We studied the parameterized complexity of MaxSTP. We began by giving a general W[1]-hardness proof that extended to any graph parameter. This necessitated a multi-parameterized with magnitude being a promising starting point. Together with vertex cover size it can either be used directly for an FPT algorithm, or, when combined with treewidth, for an XP algorithm. Naturally, the map of the parameterized complexity landscape of MaxSTP is not complete, and the complexity status of many interesting additional parametrizations is wide open. For example, can the FPT algorithm for vc be extended to e.g. tree-depth? If this is possible, path-width would be a logical next step where it should be feasible to either extend the FPT algorithm or to prove W[1]-hardness (similar to treewidth). For XP algorithms one could also investigate more general parameters such as clique-width or twin-width. Acknowledgments Authors are given in alphabetical order. The research of the first author was funded in whole or in part by Excellence Center at Linköping – Lund in Information Technology (ELLIIT) funded by the Swedish government and the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. The third and fifth authors are partially supported by the Swedish Research Council (VR) under grant 2021-04371. The fourth author is partially supported by VR under grant VR-2022-03214 and VR-2025-04487. References [1] J. F. Allen (1983) Maintaining knowledge about temporal intervals. Communications of the ACM 26 (11), p. 832–843. Cited by: §5. [2] F. Bacchus, M. Järvisalo, and R. Martins (2021) Maximum satisfiability. In Handbook of Satisfiability, A. Biere, M. Heule, H. van Maaren, and T. Walsh (Eds.), Frontiers in Artificial Intelligence and Applications, Vol. 336, p. 929–991. Cited by: §1. [3] M. Bannach and M. Hecher (2024) Structure-guided cube-and-conquer for MaxSAT. In NASA Formal Methods, N. Benz, D. Gopinath, and N. Shi (Eds.), Cham, p. 3–20. External Links: ISBN 978-3-031-60698-4 Cited by: §1. [4] J. Berg, M. Järvisalo, R. Martins, A. Niskanen, and T. Paxian (Eds.) (2024) MaxSAT evaluation 2024: solver and benchmark descriptions. Department of Computer Science Series of Publications B, Department of Computer Science, University of Helsinki (English). Cited by: §1. [5] U. Bertelé and F. Brioschi (1972) Nonserial dynamic programming. Academic Press. Cited by: §2.3. [6] L. Bertossi and J. Chomicki (2004) Query answering in inconsistent databases. In Logics for Emerging Applications of Databases, p. 43–83. Cited by: §1. [7] M. Bodirsky and P. Jonsson (2017) A model-theoretic view on qualitative constraint reasoning. Journal of Artificial Intelligence Research 58, p. 339–385. Cited by: §5. [8] H. L. Bodlaender and A. M. C. A. Koster (2008) Combinatorial optimization on graphs of bounded treewidth. The Computer Journal 51 (3), p. 255–269. Cited by: §4.2.2. [9] H. L. Bodlaender (1996) A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing 25 (6), p. 1305–1317. Cited by: §2.3. [10] J. C. Boerkoel and E. H. Durfee (2013) Distributed reasoning for multiagent simple temporal problems. Journal of Artificial Intelligence Research 47 (1), p. 95–156. External Links: ISSN 1076-9757 Cited by: §1. [11] S. Chien, B. Smith, G. Rabideau, N. Muscettola, and K. Rajan (1998) Automated planning and scheduling for goal-based autonomous spacecraft. IEEE Intelligent Systems and their Applications 13 (5), p. 50–55. External Links: Document Cited by: §1. [12] J. Chomicki and J. Marcinkowski (2005) Minimal-change integrity maintenance using tuple deletions. Information and Computation 197 (1-2), p. 90–121. Cited by: §1. [13] J. Condotta, A. Mensi, I. Nouaouri, M. Sioutis, and L. B. Saïd (2016) Local search for maximizing satisfiability in qualitative spatial and temporal constraint networks. In Proc. 17th International Conference on Artificial Intelligence: Methodology, Systems, and Applications (AIMSA-2016), Vol. 9883, p. 247–258. Cited by: §1. [14] J. Condotta, I. Nouaouri, and M. Sioutis (2016) A SAT approach for maximizing satisfiability in qualitative spatial and temporal constraint networks. In Proc. 15th International Conference on the Principles of Knowledge Representation and Reasoning (KR-2016), Cited by: §1. [15] K. K. Dabrowski, P. Jonsson, S. Ordyniak, and G. Osipov (2022) Resolving inconsistencies in simple temporal problems: A parameterized approach. In Proc. of the 36th AAAI Conference on Artificial Intelligence (AAAI-2022), p. 3724–3732. Cited by: §1, §1, §1. [16] K. K. Dabrowski, P. Jonsson, S. Ordyniak, and G. Osipov (2023) Solving infinite-domain CSPs using the patchwork property. Artificial Intelligence 317, p. 103880. Cited by: §5. [17] K. K. Dabrowski, P. Jonsson, S. Ordyniak, and G. Osipov (2024) Algorithms and complexity of difference logic. CoRR abs/2402.03273. Cited by: §3. [18] R. Dechter, I. Meiri, and J. Pearl (1991) Temporal constraint networks. Artificial intelligence 49 (1-3), p. 61–95. Cited by: §1, §1, §2.2, §2.2, §4.1. [19] R. Dechter (1999) Bucket elimination: a unifying framework for reasoning. Artificial Intelligence 113 (1), p. 41–85. External Links: Document, ISSN 0004-3702 Cited by: §2.3. [20] H. Dell, E. J. Kim, M. Lampis, V. Mitsou, and T. Mömke (2017) Complexity and approximability of parameterized MAX-CSPs. Algorithmica 79 (1), p. 230–250. Cited by: §1. [21] R. G. Downey and M. R. Fellows (2013) Fundamentals of parameterized complexity. Springer. Cited by: §2.3. [22] F. Dylla, J. H. Lee, T. Mossakowski, T. Schneider, A. van Delden, J. van de Ven, and D. Wolter (2017) A survey of qualitative spatial and temporal calculi: algebraic and computational properties. ACM Computing Surveys 50 (1), p. 7:1–7:39. Cited by: §5. [23] L. Eriksson and V. Lagerkvist (2023) A fast algorithm for consistency checking partially ordered time. In Proc. 32nd International Joint Conference on Artificial Intelligence (IJCAI-2023), p. 1911–1918. Cited by: §5. [24] L. Eriksson and V. Lagerkvist (2023) Improved algorithms for Allen’s interval algebra by dynamic programming with sublinear partitioning. In Proc. 32nd International Joint Conference on Artificial Intelligence (IJCAI-2023), p. 1919–1926. Cited by: §5, §5. [25] J. Flum and M. Grohe (2006) Parameterized complexity theory. Springer. Cited by: §2.3. [26] A. U. Frank (1991) Qualitative spatial reasoning with cardinal directions. In Proc. 7th Austrian Conference on Artificial Intelligence (ÖGAI-1991), p. 157–167. Cited by: §5. [27] A. S. Fukunaga, G. Rabideau, S. Chien, and D. Yan (1997) ASPEN: a framework for automated planning and scheduling of spacecraft control and operations. In Proceedings of the International Symposium on Artificial Intelligence, Robotics and Automation in Space (i-SAIRAS), Cited by: §1. [28] R. K. Goyal (2000) Similarity assessment for cardinal directions between extended spatial objects. Ph.D. Thesis, University of Maine. Cited by: §5. [29] L. Hunsberger and R. Posenato (2021) Simple temporal networks: a practical foundation for temporal representation and reasoning. In Proc. 28th International Symposium on Temporal Representation and Reasoning (TIME-2021), p. 1:1–1:5. Cited by: §1. [30] R. M. Karp (1972) Reducibility among combinatorial problems. Complexity of Computer Computations, p. 85–103. External Links: Document, Link Cited by: §4. [31] V. Lagerkvist, J. Groven, and L. Eriksson (2026) Towards single exponential time for temporal and spatial reasoning: a study via redundancy and dynamic programming. In Proc. 40th AAAI Conference on Artificial Intelligence (AAAI-2026), Vol. , p. . Cited by: §5. [32] G. Ligozat (1998) Reasoning about cardinal directions. Journal of Visual Languages and Computing 9 (1), p. 23–44. Cited by: §5. [33] D. Lokshtanov, D. Marx, and S. Saurabh (2011) Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS 105, p. 41–72. Cited by: Theorem 2. [34] C. Lutz and M. Miličić (2007) A tableau algorithm for description logics with concrete domains and general tboxes. Journal of Automated Reasoning 38 (1-3), p. 227–259. Cited by: §5. [35] D. Nau, M. Ghallab, and P. Traverso (2004-05) Automated planning: theory and practice. Morgan Kaufmann Publishers Inc., San Francisco, CA, United States. External Links: ISBN 978-1-55860-856-6 Cited by: §1. [36] R. Niedermeier (2006) Invitation to fixed-parameter algorithms. Oxford University Press. Cited by: §2.3. [37] D. Randell, Z. Cui, and A. Cohn (1992) A spatial logic based on regions and connection. In Proc. 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR-1992), p. 165–176. Cited by: §5. [38] N. Robertson and P. D. Seymour (1984) Graph minors. I. Planar tree-width. Journal of Combinatorial Theory, Series B 36 (1), p. 49–64. Cited by: §2.3. [39] M. Samer and S. Szeider (2010) Constraint satisfaction with bounded treewidth revisited. Journal of Computer and System Sciences 76 (2), p. 103–114. Cited by: §4.2.2. [40] I. Tsamardinos and M. E. Pollack (2003) Efficient solution techniques for disjunctive temporal reasoning problems. Artificial Intelligence 151 (1-2), p. 43–89. Cited by: §1, §2.2. [41] Z. Wang, C. Liu, and M. Gombolay (2022) Heterogeneous graph attention networks for scalable multi-robot scheduling with temporospatial constraints. Autonomous Robots 46 (1), p. 249–268. Cited by: §1.