---
title: "Maximum Satisfiability of Simple Temporal Problems"
authors:
  - "Johannes K. Fichte"
  - "Johanna Groven"
  - "Peter Jonsson"
  - "Victor Lagerkvist"
  - "Jorke M. de Vlas"
doi: "10.24963/ijcai.2026/248"
url: "https://ijcai.org/proceedings/2026/248"
pdf: "https://ijcai.org/proceedings/2026/0248.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "2227-2235"
track: "Main Track"
keywords:
  - "Constraint Satisfaction and Optimization: Constraint satisfaction"
  - "Constraint Satisfaction and Optimization: Constraint optimization problems"
---

# Maximum Satisfiability of Simple Temporal Problems

Johannes K. Fichte, Johanna Groven, Peter Jonsson, Victor Lagerkvist, Jorke M. de Vlas

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 2227-2235. DOI: [10.24963/ijcai.2026/248](https://doi.org/10.24963/ijcai.2026/248)

## 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 * 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.