# Maximum Satisfiability of Simple Temporal Problems

arXiv: https://arxiv.org/abs/2607.23785 · HTML: https://mlsanity.com/paper/2607.23785/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 44 references that are in the map.
- First posted on arXiv 26 Jul 2026.

## Builds on (most cited first, 5 of 5)

- [Solving Infinite-Domain CSPs Using the Patchwork Property](https://mlsanity.com/paper/2107.01428/) (2021)
- [Complexity and Approximability of Parameterized MAX-CSPs](https://mlsanity.com/paper/1511.05546/) (2015)
- [A Fast Algorithm for Consistency Checking Partially Ordered Time](https://mlsanity.com/paper/2305.15917/) (2023)
- [Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning](https://mlsanity.com/paper/2305.15950/) (2023)
- [Algorithms and Complexity of Difference Logic](https://mlsanity.com/paper/2402.03273/) (2024)

## Abstract (arXiv)

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)-time algorithm, yielding single-exponential solvability for fixed k. While k+tw remains W[1]-hard, MAXSTP is in XP via an 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 + vc.