Resolving Inconsistencies in Simple Temporal Problems: A Parameterized Approach

Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov

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.

Figure 1: A graph-based representation of conflicting paths (A and B) between variables s and t. Such structures are used to model temporal inconsistencies as path separation problems.

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

Abstract

The simple temporal problem (STP) is one of the most influential reasoning formalisms for representing temporal information in AI. We study the problem of resolving inconsistency of data encoded in the STP. We prove that the problem of identifying a maximally large consistent subset of data is NP-hard. In practical instances, it is reasonable to assume that the amount of erroneous data is small. We therefore parameterize by the number of constraints that need to be removed to achieve consistency. Using tools from parameterized complexity we design fixed-parameter tractable algorithms for two large fragments of the STP. Our main algorithmic results employ reductions to the Directed Subset Feedback Arc Set problem and iterative compression combined with an efficient algorithm for the Edge Multicut problem. We complement our algorithmic results with hardness results that rule out fixed-parameter tractable algorithms for all remaining non-trivial fragments of the STP (under standard complexity-theoretic assumptions). Together, our results give a full classification of the classical and parameterized complexity of the problem.
BibTeX
@inproceedings{dabrowski2022resolving,
  author = {Konrad K. Dabrowski and Peter Jonsson and Sebastian Ordyniak and George Osipov},
  title = {{Resolving Inconsistencies in Simple Temporal Problems: A Parameterized Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i4.20286},
}
Figure