Disjunctive Temporal Problems under Structural Restrictions

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

Introduction

Temporal reasoning is a fundamental component of artificial intelligence, essential for applications ranging from autonomous robot scheduling to complex bioinformatics data analysis. At its simplest, this involves the Simple Temporal Problem (STP), where constraints are linear (e.g., "Event A must occur between 5 and 10 minutes after Event B"). While STPs are efficiently solvable, real-world applications often demand disjunctive logic—Disjunctive Temporal Problems (DTPs)—to model scenarios like "Task A must happen either before or after Task B."

This added flexibility comes at a significant computational cost: DTPs are generally NP-hard. This paper investigates whether structural restrictions, specifically treewidth ($w$), can render these problems tractable. By mapping the complexity landscape, the authors identify the "sweet spots" where DTPs become solvable in polynomial time and where they remain fundamentally difficult.

Problem Framework and Parameters

The authors analyze DTPs through the lens of parameterized complexity, focusing on two primary variables:

  1. Treewidth ($w$): This measures the "tree-likeness" of the constraint network. A low treewidth suggests a sparse, less complex interaction between variables.
  2. Numeric Bounds ($k$): This represents the maximum absolute value of integers used within the constraints.

The study distinguishes between different representations of problem structure, specifically the incidence graph versus the primal graph, noting that for infinite-domain problems like DTPs, these choices significantly impact complexity results.

Algorithmic Approach: The XP Algorithm

The core positive result of the paper is a new dynamic programming algorithm designed for DTPs with bounded integers. The algorithm operates on a "nice tree decomposition" of the problem's incidence graph.

By partitioning the problem into a tree of "bags"—small, manageable sets of variables and constraints—the algorithm processes the structure from the leaves to the root. It maintains a compact representation of partial solutions that are consistent across the tree. The resulting complexity is $(nk)^{O(w)}$, placing the problem in the complexity class XP. This means that for a fixed treewidth, the problem is solvable in polynomial time, though the exponent depends on the treewidth.

Hardness and the Limits of Tractability

To define the boundaries of what is computationally feasible, the authors employ mathematical reductions to known hard problems. They demonstrate that while bounded-integer DTPs are in XP, they are likely not Fixed-Parameter Tractable (FPT). In FPT problems, the exponential part of the runtime is independent of the input size $n$; for DTPs, the exponent grows with the treewidth.

Construction for the hardness reduction showing buckets and garbage collection zones.

The research highlights a critical "Integer Gap." If the integers in the constraints are allowed to be unbounded, the problem becomes pNP-hard. In this regime, even a very small constant treewidth (e.g., $w=2$) does not prevent the problem from being NP-hard. This suggests that the magnitude of the time offsets is as critical to complexity as the structural connectivity of the constraints.

The Complexity Landscape

The paper’s findings are synthesized into a comprehensive map of DTP complexity based on arity ($a$) and numeric bounds ($k$).

Complexity landscape of DTPs categorized by arity (a) and numeric bounds (k).

Key takeaways from this landscape include:

  • Bounded Integers: DTPs with integers bounded by a polynomial are in XP, solvable in $(nk)^{O(w)}$ time.
  • Binary DTPs: Even with minimal numeric values (0 and 1), the problem is W[1]-hard relative to treewidth, precluding efficient FPT algorithms.
  • Unbounded Integers: The problem is pNP-hard regardless of structural simplicity.

Conclusion and Future Directions

This work establishes that structural restrictions alone are insufficient to tame the complexity of DTPs when large numeric values are involved. The dependence of the XP algorithm on the integer bound $k$ remains a hurdle for practical applications with high-precision or large-scale time offsets.

Future research may look beyond treewidth to other structural measures like clique-width, which can better characterize dense constraint networks. Additionally, exploring restrictions on the types of disjunctions allowed, rather than just the graph structure, may reveal new classes of DTPs that admit more efficient FPT algorithms.

Summary updated

Abstract

The disjunctive temporal problem (DTP) is an expressive temporal formalism that extends Dechter et al.'s simple temporal problem. The DTP is well studied in the literature and has many important applications. It is known that deciding satisfiability of DTPs is NP-hard and that, in many cases, single-exponential algorithms (running in $O(c^n)$ time) do not exist under the Exponential-Time Hypothesis. The computational hardness makes it worthwhile to identify restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints. We show that instances of DTP of any arity with integers bounded by $poly(n)$ can be solved in $n^{f(w)}$ time, where n denotes the problem size, w is the treewidth of the incidence graph and f is a computable function; in other words, this problem is in the complexity class XP and it can be solved in polynomial time whenever w is fixed. We complement this result by showing that binary DTPs that only involve the integers 0 and 1 are not fixed-parameter tractable with respect to treewidth, i.e. they do not admit a $f(w)poly(n)$ time algorithm for any computable function f, under standard complexity assumptions. For instances with unbounded integers, we show that even binary DTPs parameterized by treewidth cannot be in XP, unless P = NP.
BibTeX
@inproceedings{dabrowski2021disjunctive,
  author = {Konrad K. Dabrowski and Peter Jonsson and Sebastian Ordyniak and George Osipov},
  title = {{Disjunctive Temporal Problems under Structural Restrictions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16489},
}
Figure