Maximum Satisfiability of Simple Temporal Problems

1 Introduction

The simple temporal problem [Dechter et al., 1991] (STP) is a fundamental quantitative temporal constraint problem in AI. The task is to decide if a set of constraints (for a, b ∈ Z ∪ {-∞,∞}) of the form a ≤ x - y ≤ b, or a ≤ 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 [Hunsberger and Posenato, 2021]. Early success stories include e.g. autonomous vehicles in space exploration [Chien et al., 1998; Fukunaga et al., 1997], and temporal planning [Nau et al., 2004, Chapter 14] while more recent examples include e.g. managing temporal data in robotic scheduling [Wang et al., 2022] and multi-agent systems [Boerkoel and Durfee, 2013].

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 [Dechter et al., 1991; Tsamardinos and Pollack, 2003], and, more recently [Dabrowski et al., 2022], 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 [Condotta et al., 2016a; Condotta et al., 2016b; Chomicki and Marcinkowski, 2005; Bertossi and Chomicki, 2004] and the references therein). Its Boolean analogue is the ubiquitous MAXSAT problem where clauses in Boolean CNF are considered [Bacchus et al., 2021]. An annual solver evaluation (MAXSAT Evaluation) collects applications, and instances, and tests solvers practically [Berg et al., 2024].

Hence, we study the problem MAXSTP: given an STP instance and m ≥ 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 [Dabrowski et al., 2022] 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) time, where I is an instance with parameter k ∈ N, ||I|| the number of bits required to represent it, and f : N → N 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. [Dell et al., 2017]) and recently also solvers that employ and improve on parameterized techniques (such as treewidth) have been introduced [Bannach and Hecher, 2024]. 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 [2022] 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 mag(C), the largest absolute value of any constant appearing in an instance (V, C). Towards FPT algorithms we first (in Section 3) investigate the parameterized complexity of MAXSTP with parameter n = |V |. Observe that this for many problems, e.g., finitedomain 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 mag(C)n , i.e., for fixed magnitude 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(n logmag(C)+f(n)) time for any computable function f : N → N, 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 | 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), where we get FPT for 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∗ (·) 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(A)) is defined as follows:

CSP(A)

Input: A tuple (V,C), where V is a set of vari-

ables and C is a multiset of constraints of the formR(v1, . . . , va), where a is the arity of R, v1, . . . , va ∈ V , and R ∈ A. Question: Is there a function f : V → D such that (f(v1), . . . , f(va)) ∈ R for every

R(v1, . . . , va) ∈ 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) is the number of constraints in C satisfied by φ. The maximum constraint satisfaction problem (MAXCSP(A)) is defined as follows:

MAXCSP(A)

Input: An instance (V,C) of CSP(A) and an integer m.

Question: Is there a set X ⊆ C such that |X| ≥m and (V,X) is satisfiable?

Given an instance ((V,C),m) of MAXCSP(A), the set X can be computed with |C| calls to an algorithm for MAXCSP(A). Hence, we can view MAXCSP(A) as a decision problem without loss of generality.

The primal graph of a CSP instance (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. [1991] introduced the highly influential simple temporal problem. Let Sb be the set of binary relations

for endpoints a ∈ Z ∪ {-∞} and b ∈ Z ∪ {∞} such that a ≤ b, (a, b) ̸= (-∞,∞). Let Su be the set of unary relations Ua,b = {(x) ∈ Q | a ≤ x ≤ b} for endpoints a ∈ Z ∪ {-∞} and b ∈ Z∪{∞} such that a ≤ b, (a, b) ̸= (-∞,∞). CSP(S) where S = Sb ∪ Su is known as the simple temporal problem (STP). To aid readability, we sometimes denote the constraint Ra,b(x, y) by a ≤ x-y ≤ b. We follow e.g. [Tsamardinos and Pollack, 2003] and assume that bounding values are integers. This implies that every satisfiable instance of STP admits an integer solution (see Dechter et al. [1991, Section 3]). We can thus work over Z without loss of generality.

Given an STP relation Ra,b, we let mag(Ra,b) = max({|a|, |b|} \ {∞}). We say that mag(Ra,b) is the magnitude of Ra,b. Note that the magnitude of, for instance, R1,∞

is 1. If X is a set of relations or constraints, then the definition of mag(·) extends naturally: mag(X) = maxR∈X mag(R), i.e. 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) and MAXSTPb denote MAXSTP restricted to binary relations. We will look at restricted versions of MAXSTP so we let S(k) , k ∈ N, denote S restricted to relations R satisfying mag(R) ≤ k and let MAXSTP(k) denote MAXCSP(S(k) ) (and MAXSTP(k) b is defined in the obvious way).

We finally note that the CSP(Sb) problem is invariant under translation, i.e. if φ : V →Z satisfies an instance (V,C), then so does φ′ (v) = φ(v)+c for all v ∈ V and an arbitrary c ∈ Z. 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 Sb, e.g. the constraint 0 ≤ x - z ≤ 2 is equivalent to x ∈ {0, 1, 2}.

2.3 Parameterized Complexity

We use the framework of parameterized complexity [Downey and Fellows, 2013; Flum and Grohe, 2006; Niedermeier, 2006], where the run-time of an algorithm is studied with respect to a parameter p ∈ N 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) time, where f is a computable function. The next best option is the complexity class XP, which contains all problems decidable in nf(p) time, i.e. the problems solvable in polynomial time when the parameter p is bounded. Clearly, FPT ⊆ XP and this inclusion is strict (see e.g. [Flum and Grohe, 2006, 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) time by a nondeterministic 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 L1 and L2 denote parameterized problems with L1 ⊆ Σ∗1 × N and L2 ⊆ Σ∗2 × N. A parameterized reduction from L1 to L2 is a mapping P : Σ∗1 ×N→Σ∗2 ×N such that

1. (x, k) ∈ L1 if and only if P((x, k)) ∈ L2,
2. the mapping can be computed by an FPT-algorithmwith respect to the parameter k, and
3. there is a computable function g : N→N such that for all (x, k) ∈ L1 if (x′ , k′ ) = P((x, k)), then k′ ≤ g(k).

The class W[1] contains all problems that are FPT-reducible to INDEPENDENT SET parameterized by the size of the solution set. Showing W[1]-hardness (by an FPT-reduction) for a problem rules out the existence of an FPT algorithm under the assumption 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) 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 Robertson and Seymour [1984], the idea appeared much earlier in nonserial dynamic programming [Bertel´e and Brioschi, 1972] and have been intensively applied in AI (e.g. bucket elimination [Dechter, 1999]). A tree decomposition T = (T, χ) of a graph G = (V, E) consists of a rooted tree T and a mapping χ that assigns each node t ∈ V (T ) a set χ(t) ⊆ V , called bag, such that (i) E(G) ⊆ {{u, v} | t ∈ V (T), {u, v} ⊆ χ(t)}; and (ii) for every v ∈ V , the nodes, for which the bag contains v, form a non-empty sub-tree of T . We let width(T ) = max{|χ(t)|-1 : t ∈ T}. The treewidth of a graph G, denoted by tw(G), is the minimum 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 ≥ 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 [Bodlaender, 1996].

3 BoundedMagnitude is Necessary

Exhaustive enumeration of all subsets of constraints solves MAXSTP in O∗ (2|C| ) ⊆ O∗ (2||I|| ) time where ||I|| is the number of bits required to represent the instance I. Since ||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 mag(C)n , i.e., 2n logmag(C) . Thus, MAXSTP is solvable in single-exponential time for any fixed magnitude.

Theorem 1. MAXSTPb can be solved in O∗ ((k + 3)n ) time, where n = |V | and 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 + 3 groups: one group A< containing vertices more than k below the boundary value, k + 1 groups A0, . . . , Ak containing variables exactly 0, . . . , k below the boundary value, and one group A> containing vertices at or above the boundary value. Note that the vertices at the boundary value can be either in A0 or in A>. Overall, this results in (k + 3)n states. We call variables in A<, A0, . . . , Ak as decided and variables in A> as undecided.

The algorithm starts in the state where A< = A0 = . . . = Ak = ∅ and A> = V and recursively moves variables from A> to A<, maintaining that for each configuration (A<, A0, . . . , Ak, 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> to group A0. 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 ≤ k, we have v - u = i. For all u ∈ A<, we have 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< and Ak into a new group A<, relabels each group Ai as Ai+1 for i ∈ {0, . . . , k - 1}, and adds a new empty group A0. 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, . . . ,Ak are all empty as we can assume that without loss of generality, the gap between two variables will be at most k + 1 by k = mag(C).

Clearly, each path from the starting state to the final state (A< = V ) using these transitions corresponds to a potential solution to the MAXSTPb instance, and each potential solution corresponds to such a path. We now show in which order to visit all the states. Consider the quantity

In the first transition, we add one variable to |A0|, hence this quantity increases by one. In the second transition, each variable from the groups A0, . . . , Ak 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 instance. Since there are (k + 3)n states, each state has at most n+1 transitions, and each transition can be computed in linear time, the total runtime is O∗ ((k + 3)n ).

We complement this upper bound by a matching lower bound (under standard complexity theoretical assumptions) for the parameter 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) with a vertex coloring fC : V → C to some color set C such that each edge is between vertices of different colors.

Param.: The number of colors |C|

Question: Is there a clique in G with exactly one vertex from each color?

Table 1: The set S = {0, 1, 4, 6} is a Sidon set: a - b has distinct values whenever a ̸= b and a, b ∈ S.

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 + d for a, b, c, d ∈ S, then {a, b} = {c, d}. Differences are easier to use in our proofs so we use an equivalent condition: for all a, b, c, d ∈ S such that a ̸= b and c ̸= d, a - b = c - d holds if and only if a = c and b = 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} is a Sidon set (see Figure 1) of order 4 with length 6. It is well-known that "reasonable" Sidon sets are computable in polynomial time. For instance, Dabrowski et al. [2024, Section 2.3] describe how a Sidon set of order k and length 8k2 can be computed in polynomial time.

Theorem 3. MAXSTPb (and thus MAXSTP) is W[1]-hard when parameterized by the number of variables. It cannot be solved in 2o(n log k+f(n)) time unless the ETH fails where n = |V | is the number of variables, k = mag(C) the magnitude, and f : N → N any computable function.

Proof. We present a reduction fromMULTICOLOR CLIQUE to an instance of MAXSTPb. Let (G = (V,E), fC) be an instance of MULTICOLOR CLIQUE with n vertices, m edges and c = |C| colors. We begin by introducing variables x1, . . . , xc for each color and a zero variable z. We construct a Sidon set S = {s1, . . . , sn} and add the constraints xfC(1)-z = s1, xfC(2)-z = s2, . . . xfC(n)-z = sn, which we make costly to delete by repeating them m+ 1 times. Additionally, for each edge (u, v) ∈ E, we add the constraint xfC(u) - xfC(v) = su - sv. This completes our reduction. Note that we now have (m + 1)n + m constraints.

Let W := {z, x1, . . . , xc} the resulting set of variables and D the resulting set of constraints. Clearly, (W,D) can be computed in polynomial time. We now verify that G contains a multicolored clique if and only if ((W,D),N) is a yesinstance of MAXSTPb where N := c(m + 1) + (c2).

Forward direction. Assume G contains a multicolored clique K. Let g : C → K denote for each color the vertex from K that has this color. Define h: W → Z such that h(z) = 0 and h(xi) = sg(i). We show that h is a solution to the MAXSTPb instance. Each edge (u, v) ∈ K corresponds to the constraint xfC(u) - xfC(v) = su - sv. Since h(xfC(u)) - h(xfC(v)) = sg(fC(u)) - sg(fC(v)) = su - sv, these (c2) constraints are satisfied. For each vertex v ∈ K, consider the constraint xfC(v) - z = sv, which was repeated m+ 1 times. Since h(xfC(v)) - h(z) = sg(fC(v)) - 0 = sv, we also satisfy this, resulting in an additional c(m+ 1) satisfied constraints. In total, we satisfy at least N constraints.

Backward direction. Assume ((W,D),N) is a yes-instance and let h : W → Z be a solution. By globally adding a suitable constant, we assume that h(z) = 0.

For each variable xi, all constraints between xi and z are disjoint up to the m+1 time repetition, hence we satisfy either 0 or m+1 such constraints. Since there are only m constraints not of this form, we must satisfy m+ 1 such constraints for each variable; if not, we satisfy at most (c-1)(m+1)+m < c(m+ 1) < N constraints. It follows that xi is assigned a value su for some u ∈ V with fC(u) = i. Let g : C → V be the function mapping each i to the corresponding u.

Now consider two variables xi and xj . As S is a Sidon set, and both xi and xj are assigned values from S, every constraint of the form xfC(u) -xfC(v) = su -sv with fC(u) = i and fC(v) = j is only satisfied if xi is assigned su and xj is assigned sv. It follows that we can only satisfy at most one such constraint between xi and xj .

In order to satisfy c(m+ 1) + (c2) constraints in total, we must satisfy exactly one such constraint for each pair (xi, xj) as there are no other remaining constraints. This shows that, for each xi and xj, the constraint xi - xj = sg(i) - sg(j) must exist. That is, g(i) and 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 + 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 < 8n2 , any algorithm solving MAXSTP in 2o(n′ log k′+f ′ (n′ )) time for some f ′ can be used to solve MULTICOLOR CLIQUE in

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 : N → N where f(k) is the κ of a clique on k vertices is computable. Let G = (V, E) be an instance of the MULTICOLOR CLIQUE problem with n′ variables and k′ colors. We use the same reduction as in the proof of Theorem 3. The primal graph of (W, D) is now a clique on n = k′ + 1 vertices hence κ of primal graph is 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 is pNP-hard when parameterized by mag.

Proof. We use the following NP-hard problem [Karp, 1972].

MAXIMUM ACYCLIC SUBGRAPH (MAS)

Input: A directed graph D = (V,A) and an integer m.

Question: Is there a set X ⊆ A such that |X| ≥m and (V,X) is acyclic?

Let ((V, A), m) be an arbitrary instance of MAS. Construct an instance ((V, C), m) of MAXSTPb where each arc vw ∈ A is replaced by the constraint v - w ≤ -1. This constraint can be viewed as enforcing that f(v) < f(w) for any solution f. It is clear that ((V,A),m) is a yes-instance if and only if ((V,C),m) is a yes-instance. Furthermore, mag(C) ≤ 1 so MAXSTPb 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) of CSP, we let 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). This graph is constructed by for each constraint a ≤ x - y ≤ b in C, adding arcs (x, y), (y, x) to A with weights w(x, y) = b, w(y, x) = -a. Arcs of infinite weight are not added to A. Dechter et al. [1991, Theorem 3.1]) have noted the following: an instance I of CSP(S) is satisfiable if and only if ∆I contains no directed cycle of total negative weight.

Lemma 6. Let I = (V,C) be an instance of Sb where k = mag(C) is its magnitude and d is the length of the longest simple path in the distance graph ∆I. If I has a solution, it has one where each value comes from the set {0, 1, 2, . . . , dk}.

Proof. Consider the distance graph ∆I. Since I has at least one solution, ∆I has no directed cycles of negative weight. Modify ∆I by adding a zero vertex z together with an arc of weight zero from each other vertex to z and let f : V → Z be the function where, for each x ∈ V , f(x) is the length of the shortest path from x to z, measured by arc weight. This shortest distance exists since ∆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 is a solution satisfying the lemma.

First, -f is a solution to the instance: if some constraint x - y ≤ c is not satisfied, then the path from x to z could be made shorter by going via y. Furthermore, -f is at least zero since f is non-positive. Finally, -f is at most dk 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) have a solution that only uses values from the set {0, 1, 2, . . . , (n - 1)k} where n = |V | and k = mag(C).

Theorem 7. MAXSTPb can be solved in O∗ ((2vc · 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 2vc + 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, . . . , (2vc + 1)k}.

We now describe our algorithm. Let W with |W| = vc be a vertex cover. For each variable in W, guess a value from A. This results in |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| 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

4.2 Treewidth

We show that MAXSTP(k) b is W[1]-hard when parameterized by treewidth of primal graph for every k ≥ 1 (MAXSTP(0) b 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)tw time where k = mag(C) and n = |V |.

W[1]-hardness

Our W[1]-hardness result is based on the proof of Theorem 3.

Theorem 8. MAXSTP(1) b 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 whose primal graph is a clique on c + 1 vertices and each edge corresponds to an equality constraint of magnitude at most 8n2 , 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) 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) corresponding to a constraint f(x) - f(y) = a with |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, . . . , xa where x0 = x, xa = y, and x1, . . . , xa-1 are fresh variables. Each edge (xi-1, xi) is given the constraint f(xi-1) - f(xi) = 1. The result is a graph on O(mn · n2 ) 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), which implies that the reduction is FPT and hence that MAXSTP(1) b is W[1]-hard when parameterized by tw. We begin with one bag B containing all c + 1 vertices from the original clique. For each path x0, x1, . . . , xa, we add a path of bags B1, . . . ,Ba with Bi := {xi-1, xi, y} for 1 ≤ i ≤ a and where B1 is adjacent to B. This results in a valid tree decomposition. The size of the largest bag is max(3, c + 1), hence the width is max(2, c), which completes the proof.

XP Algorithm

We continue with our XP algorithm.

Theorem 9. MAXSTPb can be solved in O∗ ((nk)tw ), where n is the number of vertices, k the magnitude, and tw the treewidth of the distance graph ∆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) = ∅, and each node t has one of the following types:

• leaf node: χ(t) = ∅ and t has no children.
• introduce node: t has one child t′ , and there exists a vertex v ∈ χ(t) such that χ(t′ ) = χ(t) \ {v}.
• forget node: t has one child t′ , and there exists a vertex v ∈ χ(t′ ) such that χ(t) = χ(t′ ) \ {v}.
• join node: t has two children t1, t2 and χ(t) = χ(t1) = χ(t2).

Any tree decomposition can be modified into a nice tree decomposition of the same width in linear time. For a node t ∈ T, we define Tt as the subtree rooted at t, and define χ(Tt) = ⋃t′∈Tt χ(t′ ) as the set of all variables occurring in this subtree [Bodlaender and Koster, 2008].

We use standard dynamic programming over a tree decomposition [Samer and Szeider, 2010]. Let T be a nice tree decomposition of the primal graph ∆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 Ct denote the constraints associated with t.

By Lemma 6, noting that any simple path has length at most n - 1, we only need to look for solutions from the set S = {0, 1, 2, . . . , (n - 1)k}. We now wish to compute the following information: for each node t, and each possible assignment f : χ(t) → S, what is the largest number of constraints that can be satisfied in any extension of f into an assignment f ′ : χ(Tt) → S where we only consider constraints that are associated with nodes from Tt? Let DP(t, f) denote this value.

Given t and f, we note that DP(t, f) equals the number of constraints in Ct satisfied by f plus the following depending on the type of t.

• leaf node: Tt contains no other constraints, hence we add nothing.
• introduce node: let t′ be the child node. Any extension of f must extend the restriction f|χ(t′ ) , hence we add the value DP(t′ , f|χ(t′ ) ).
• forget node: let t′ be the child node and v the forgotten variable. For each i ∈ S, let fi be the extensions of f into an assignment of χ(t′ ) where fi(v) = i. Since any extension of f in χ(Tt) extends some fi, we add the maximum maxi∈S (DP (t′ , fi)).
• join node: let t1 and t2 be the two child nodes. Since any extension of f to χ(Tt) can be split into two independent extensions f1 in χ(Tt1 ) and f2 in χ(Tt2 ), we add the sum DP (t1, f ) + DP (t2, f ).

Finally, since the root r is empty, DP(r, ∅) holds the answer to the entire instance. For all nodes t except forget nodes, there are at most |S|tw+1 states and each state can be computed in O(|Ct|) time. For forget nodes t, each state requires O(|S| + |Ct|) time, but we have |χ(t)| < tw+1 since the child node is larger and has size at most tw + 1, hence computing all states also requires O(|S|tw+1 |Ct|) time. Since there are O(n) nodes total, and all Ct sum to m, the total runtime is O(|S|tw+1 (n+ m)) = O((nk)tw ).

5 AComparison 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 [Allen, 1983], the spatial RCC formalisms [Randell et al., 1992], and various cardinal direction calculi [Frank, 1991; Goyal, 2000; Ligozat, 1998]. The intersection between qualitative reasoning and CSPs has been intensively studied, generating a large number of formalisms and results [Bodirsky and Jonsson, 2017; Dylla et al., 2017]. 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 [Eriksson and Lagerkvist, 2023a; Eriksson and Lagerkvist, 2023b] 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. [2023] have proven that CSP(A) for constraint languages with the patchwork property (see [Lutz and Miliˇci´c, 2007]) 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(A) is decidable in a time f(n) for some f(n) ∈ Ω∗ (exp(n)) using DP and a search tree such that
• any two nodes in the tree that are equivalent to each other (v ∼ 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(A) is solvable in time 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 problemMAXCSP(B) is FPT parameterized by the treewidth of the primal graph.

Consider Algorithm 2 from [Eriksson and Lagerkvist, 2023b] that solves CSP(Allen) in time O∗ ((cn/ logn)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/ log 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 [Lagerkvist et al., 2026] showing a O∗ ((cn/ logn)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/ log 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¨oping - 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.