Maximum Satisfiability of Simple Temporal Problems

Simple Temporal Problems (STP) are a standard framework for modeling quantitative temporal constraints. While checking the consistency of an STP instance is solvable in polynomial time, real-world data is often inconsistent. This paper investigates the computational complexity of MAXSTP, which seeks the largest subset of constraints that can be satisfied simultaneously. The authors aim to identify which instance parameters—such as the number of variables, numeric magnitude, or graph structure—allow for efficient (fixed-parameter tractable) solutions.

The authors analyze MAXSTP through the lens of parameterized complexity. They evaluate the problem against several parameters: the number of variables (n), the maximum coefficient magnitude (k), and structural graph parameters like treewidth (tw) and vertex cover size (vc). They employ dynamic programming to establish upper bounds and use reductions from the MULTICOLOR CLIQUE problem to establish W[1]-hardness, effectively ruling out certain FPT algorithms unless standard complexity assumptions (like the Exponential Time Hypothesis) are violated.

The study demonstrates that MAXSTP is significantly harder than its qualitative counterparts (such as Allen's interval algebra). Specifically:

• MAXSTP is W[1]-hard when parameterized by the number of variables (n), which implies that parameters depending on n, such as treewidth and vertex cover, are also insufficient for FPT.
• The problem is solvable in O*((k+3)^n) time, making it single-exponential for fixed magnitudes.
• While treewidth alone does not yield FPT, the problem is in XP via an O*((n·k)^tw) algorithm.
• FPT algorithms are possible when using combined parameters, such as the magnitude of coefficients (k) plus the vertex cover size (vc).

This research clarifies the boundary between tractable and intractable temporal reasoning. By showing that MAXSTP is fundamentally harder than qualitative constraint satisfaction, the authors provide a theoretical roadmap for developers of temporal solvers. It suggests that practitioners should avoid relying solely on structural graph parameters like treewidth and instead look toward combined parameters involving the numeric range of the constraints to achieve efficient performance.