In 2005 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 temporal variables and a finite set of temporal constraints. Any constraint can be of one of the following three types:
(Type-1) , (a simple temporal difference constraint);
(a single-variable disjunction of many interval constraints);
(Type-3) , (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, Kumar 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 them, significantly improving the asymptotic running times of both the deterministic and randomized algorithms of Kumar. 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 Type-1 and Type-2 constraints (and no Type-3 constraint). As a second main contribution, we study the tractability frontier of solving RDTPs by considering Hyper Temporal Networks (HTNs), a strict generalization of STNs grounded on hypergraphs: on one side, we prove that solving temporal problems having either only multi-tail or only multi-head hyperarc constraints and Type-2 constraints, it lies in and it admits deterministic pseudo-polynomial time algorithms; on the other side, solving problems with either only multi-tail or only multi-head hyperarc constraints and Type-3 constraints, it turns strongly NP-complete.