In 2005 T.K.S. Kumar studied the Restricted Disjunctive Temporal Problem (RDTP), a restricted but very expressive class of Disjunctive Temporal Problems (DTPs). An RDTP comes with a finite set of time-point variables, and a finite set of temporal constraints where each of them can be either one of the following three types: () , for real (a simple temporal difference-constraint);

() , for reals (a single-variable disjunction of many interval-constraints);

() , for reals (a two-variable disjunction of two interval-constraints only).

Kumar showed that RDTPs are solvable in deterministic strongly-polynomial time by reducing them to the Connected Row-Convex (CRC) constraints problem; plus, he devised a randomized algorithm whose expected running time is less than that of the deterministic one. Instead, the most general form of DTPs allows for multi-variable disjunctions of many interval constraints and it is NP-complete.

This work offers a deeper comprehension on the tractability of RDTPs, leading to an elementary deterministic strongly-polynomial time algorithm for solving them,

significantly improving the asymptotic running times of all the previous deterministic and randomized algorithms. The result is obtained by reducing RDTPs to the Single-Source Shortest-Paths (SSSP) and the 2-SAT problem (jointly), instead of reducing to CRCs. In passing, we obtain a faster (quadratic time) algorithm for RDTPs having only and -constraints (and no -constraint).

As a second main contribution, we study the tractability frontier of solving RDTPs blended with Hyper Temporal Networks (HyTNs), a strict generalization of Simple Temporal Networks (STNs) grounded on hypergraphs: we prove that solving temporal problems having only -constraints and either only multi-tail or only multi-head hyperarc-constraints lies in and it admits deterministic pseudo-polynomial time algorithms; on the other hand, problems having only -constraints and either only multi-tail or only multi-head hyperarc-constraints are strongly NP-complete.

Download: manuscript.