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^*(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.
BibTeX
@inproceedings{ijcai2026_maximumsatisfiab,
title = {Maximum Satisfiability of Simple Temporal Problems},
author = {Johannes K. Fichte and Johanna Groven and Peter Jonsson and Victor Lagerkvist and Jorke M. de Vlas},
booktitle = {IJCAI 2026},
year = {2026}
}