# On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier.

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 $\mathcal{T}=\{X,Y,\ldots\}$ of time-point variables, and a finite set $\mathcal{C}$ of temporal constraints where each of them can be either one of the following three types: ($\texttt{t}_1$) $(Y-X\leq w)$, for $w$ real (a simple temporal difference-constraint);
($\texttt{t}_2$) $(l_1\leq X\leq u_1)\vee \cdots \vee (l_k\leq X\leq u_k)$, for $l_i,u_i$ reals (a single-variable disjunction of many interval-constraints);
($\texttt{t}_3$) $(l_1\leq X\leq u_1) \vee (l_2\leq Y\leq u_2)$, for $l_i,u_i$ 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 $\texttt{t}_1$ and $\texttt{t}_2$-constraints (and no $\texttt{t}_3$-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 $\texttt{t}_2$-constraints and either only multi-tail or only multi-head hyperarc-constraints lies in $\text{NP}\cap \text{co-NP}$ and it admits deterministic pseudo-polynomial time algorithms; on the other hand, problems having only $\texttt{t}_3$-constraints and either only multi-tail or only multi-head hyperarc-constraints are strongly NP-complete.