Maximum Satisfiability of Simple Temporal Problems

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.