Abstract
Resolving inconsistencies in temporal data is a fundamental challenge in AI planning and scheduling. While the problem of finding the minimum set of constraints to remove to restore consistency (ALMOSTCSP) is generally NP-hard, this research applies parameterized complexity to identify tractable subclasses. We provide a complete classification, demonstrating that while one-sided and equation-based constraints are Fixed-Parameter Tractable (FPT), the general Simple Temporal Problem (STP) involving interval constraints remains W[1]-hard.
Introduction
The Simple Temporal Problem (STP) provides a framework for representing timing information as a set of linear constraints, such as $a \leq x_j - x_i \leq b$. While checking the consistency of an STP is computationally efficient, real-world applications often encounter inconsistent datasets due to sensor noise or human error. The goal then becomes finding the smallest number of constraints ($k$) whose removal makes the system consistent. Historically, this problem has been proven NP-hard, prompting the need for more nuanced complexity analysis.
A Parameterized Perspective
Instead of focusing solely on the total number of constraints ($n$), the authors utilize parameterized complexity analysis. By treating the number of errors $k$ as the parameter, they seek Fixed-Parameter Tractable (FPT) algorithms. These algorithms are efficient when the number of inconsistencies is relatively small, as the exponential growth in complexity is restricted to $k$ rather than $n$.
Methodology: From Constraints to Graphs
The core of the approach involves reducing temporal constraints to graph-theoretic problems.
One-Sided and Equation Constraints
For "one-sided" constraints (e.g., $x - y \leq a$), the problem is reduced to the Directed Subset Feedback Arc Set. This involves identifying and breaking cycles in a distance graph that represent negative-weight loops, which are the source of inconsistency in these systems.
For "equation" constraints (e.g., $x - y = a$), the authors employ iterative compression. This technique involves taking a known solution and iteratively refining it into a smaller one. This process relies on an Edge Multicut subroutine to separate conflicting paths in a primal graph.
Key Results and the Complexity Dichotomy
The research establishes a sharp boundary between tractability and hardness, providing a complete "dichotomy" for STP relations:
- FPT Results: Both one-sided relations ($x - y \leq a$) and equation relations ($x - y = a$) are shown to be in FPT. Specifically, one-sided relations can be solved in $2^{k^3} \cdot n^{O(1)}$ time, while equations require roughly $2^{O(k^2 \log k)} \cdot n^{O(1)}$.
- W[1]-Hardness: The general STP, which allows for bounded interval constraints ($a \leq x - y \leq b$), is proven to be W[1]-hard. This suggests that for the most common form of temporal constraints, a small number of errors does not guarantee an efficient exact solution.
Conclusion
This work provides a rigorous classification of the parameterized complexity of resolving inconsistencies in STPs. While the W[1]-hardness of general interval constraints presents a significant hurdle, the FPT results for one-sided and equation constraints offer practical paths for specific sub-problems. Future research may explore approximation algorithms or more expressive formalisms like Allen’s Interval Algebra to bridge the gap for general temporal intervals.
Summary updated